CODEWITHSUNDEEP
recursiontreetime-complexity
weno
weno

Reputation: 856

Time complexity of tree of trees of trees of [...]

Insertion into balanced search tree is O(log n).

What'd be the time complexity of insertion into tree of trees of trees of trees of [...]? (this continues k times). So each node of the main tree is tree of trees of ... k times.

For simplicity let's assume:

Putting aside how would the balancing process work in such a structure.

My initial guess was that it's O(k log n). Any thoughts?

Upvotes: 0

Views: 119

Answers (1)

Hadi GhahremanNezhad
Hadi GhahremanNezhad

Reputation: 2445

If the main tree is just a random tree with no specific property, then to insert a new element we can search the main tree in O(n) time to find the appropriate sub-tree to insert the key in. This would be O(nlogn). However, if the main tree and all the sub-trees are balanced, then the whole thing is just a balanced tree and insert will take O(logn) as usual.

Upvotes: 1

Related Questions