CODEWITHSUNDEEP
calgorithmtime-complexitybig-o
VeVeVez
VeVeVez

Reputation: 90

Time complexity of RB Tree insertion inside a loop

I've got this doubt about how to calculate the time complexity of the following situation:

I've got a string of characters. What I want to do is cycling on all the characters and, for each one, insert a new node inside an RB-Tree.

This is the code:

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

Now, the tree is empty before the loop, and i know that the time complexity of RB-Tree insertion is O(log N) with N number of nodes inside the tree.

In this case the number of nodes inside the tree depends linearly on the value of my index i. When i=0 (first element) I have no nodes in the tree, when i=n I have n nodes in the tree.

So my question is: what is the time complexity of this code?

I was thinking about O(W * log W) where W is the length of the string but I think this is quite wrong. Then I thought that the complexity of each iteration could be:

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

But I'm not really sure this is correct...

Upvotes: 0

Views: 223

Answers (1)

Shravan40
Shravan40

Reputation: 9908

Time complexity for given piece of code

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.`

Now T2(N) is in O(nlog(n))

Hence T(N) is O(nlog(n))

Upvotes: 1

Related Questions