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
