Сложность времени вставки дерева RB внутри петли

Question

У меня есть это сомнение в том, как рассчитать временную сложность следующей ситуации:

У меня есть строка символов. То, что я хочу сделать, - это циклическое перемещение по всем символам и, для каждого, вставить новый узел внутри RB-Tree.

Это код:

int length = strlen(myString); 
    for(i=0; i<length; i++) 
     insertNodeInTree(myString[i]); 

Теперь дерево пусто перед циклом, и я знаю, что временная сложность вставки RB-дерева O (журнал N) с N числом узлов внутри дерево.

В этом случае количество узлов внутри дерева линейно зависит от значения моего индекса i. Когда i = 0 (первый элемент), у меня нет узлов в дереве, когда i = n у меня есть n узлов в дереве.

Так что мой вопрос: какова временная сложность этого кода?

Я думал о O (W * log W), где W - длина строки, но я думаю, что это совершенно неправильно. Тогда я подумал, что сложность каждой итерации может быть:

O(log 1) + O(log 2) + .... + O(log W-1) + O(log W) = O(log W!) 

Но я не совсем уверен, что это правильно ...

Answer 1

Временная сложность для данного фрагмента кода

int length = strlen(myString); 
for(i=0; i<length; i++) 
    insertNodeInTree(myString[i]); 

Т (N) = Т1 (Н) + Т2 (N) ------- (1)

T1(N) = O(n) // For calculating the Length of the string

T2(N) = O(log 1) + O(log 2) + .... + O(log n-1) + O(log n)

 `= O(log(n!)) // Insertion into RB Tree.` 

В настоящее время Т2 (N) в O (Nlog (п))

Следовательно, Т (N) представляет собой О (Nlog (п))