[Math] the lower bound and upper bound on time for inserting n nodes into a binary search tree

algorithmsasymptoticsrecursive algorithmssearching

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 :

  1. Let the empty BST be $\phi$
  2. Take each element of the array and insert into the BST $\phi$ so that after insertion the BST property of the tree still holds.
  3. 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.

Best Answer

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)$.

Related Question