log(1) + log(2) + ... + log(n) = log(1*2*..*n) = log(n!)
which is in Theta(nlogn)
So, building a (balanced) tree from scratch has a tight asymptotic bound of Theta(nlogn)
EDIT:
I also wanted to show you a proof that you cannot build a BST better than O(nlogn)
with any algorithm. Basically - this is because it will allow sorting better than O(nlogn)
by simply building your tree with the 'better' algorithm, and then - doing in-order traversal on the tree and outputting elements. The result will be a sorted array.
Complexity in-order traversal is O(n)
, and since assuming the tree is built faster then O(nlogn)
- we get contradiction to the fact that sorting is Omega(nlogn)
problen.