What is the lower bound and upper bound on time for inserting n nodes into a binary search tree? So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first  build a BST out of the array taking all the elements in order and then do an in order traversal .
So the steps will be :


*

*Let the empty BST be $\phi$

*Take each element of the array and insert into the BST $\phi$ so that after insertion the BST property of the tree still holds.

*Do an inorder traversal of the BST.


So steps 1 is $O(1)$ and step 3 is $\Theta(n)$ . I want to find out the lower and upper bounds on step 2.

The upper bound is $1+2+\dots+n = \frac{n(n+1)}{2}$ operations as the upper bound of insertion into a tree of $m$ nodes is $m$. This bound is reached is your array is sorted already.  
The lower bound is $\log(1)+\log(2)+\dots+\log(n) = \log(n!)$ as the lower bound of insertion into a tree of $m$ nodes is $\log m$.. By Stirling's approximation this is $\log (\sqrt{2 \pi n}(\frac{n}{e})^n) = \frac{1}{2}\log(2\pi n) + n(\log(n) - 1)$ which is $ O(n\log n)$. 
