Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Hint:we will get upper bound while inserting at the deepest node and lower bound while inserting at the shallowest node.Note that BST's are not height balanced. –  Saurabh Aug 20 '12 at 7:35
1  
It might be more appropriate to use cs.stackexchange.com for such questions. –  Karolis Juodelė Aug 20 '12 at 7:36

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
@The upper bound is also obtained if the array is reverse sorted , right ? –  Geek Aug 20 '12 at 7:46
    
@Geek, yes. Notice that these are not the only ways to reach it though. $2^{n-1}$ out of $n!$ orderings of the array do, I think. –  Karolis Juodelė Aug 20 '12 at 10:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.