ループ内でのRBツリーの挿入時間の複雑さ

Question

次のような状況の複雑さを計算する方法について疑問があります。

文字列があります。私がしたいことは、すべての文字をサイクリングし、それぞれについて、新しいノードをRBツリー内に挿入することです。

これはコードである：

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

次に、ツリーは、ループの前に空であり、iはRBツリーの挿入の時間複雑度は内部ノードのN番号をO（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]); 

T（N）= T1（N）+ T2（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.` 

今T2（N）O（nlog（n））をしている

したがってT（N）は[ `ログ（N O（nlog（n））を