avl tree

Question

what is the time complexity of creating an avl tree??????

Answer 1

To create an AVL tree , we have to insert n elements into it.And we know that cost of insertion in a balanced tree = O(logn)

Therefore total complexity = O(nlogn)

To be more accurate mathematically , 

No. of operations involved = log1 + log2 + log3 ..+logk ...+ logn [ Since for balanced tree of k nodes , cost of insertion = O(logk)]

                                      = log (1.2.3....n)

                                      = log n!

By Stirling's approximation , we know

log n! = O(nlogn)

Therefore , the complexity of building an AVL tree is O(nlogn)

For reference, you may visit :

http://stackoverflow.com/questions/17629668/difference-between-the-time-complexity-required-to-build-binary-search-tree-and