CODEWITHSUNDEEP
insertbinary-search-treecode-complexity
Rawhi
Rawhi

Reputation: 6413

finding the complexity of insertion to avl tree

If I have an empty avl tree and I want to insert a set of ordered numbers (1, 2, ... k), why the complexity is O(k).
thank you

Upvotes: 2

Views: 223

Answers (1)

JoeC
JoeC

Reputation: 1850

It's more of a math question, so here is the deal

AVL tree has a time complexity of log(n) for inserting an element with n nodes inside the tree

so from your question, with a set of number (1,2,3,...,k) you wanted to insert, the time complexity would be like this

summation from i=1 to i=k of log(i) (i.e. log1 + log2 + log3 + ... + logk)

which is equals to

log(k!)

which is approximately equals to

k*log(k) (By using Stirling's approximation)

So to answer your question, it should be O(k log k) instead of O(k)

Upvotes: 2

Related Questions