The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that tighter upper and lower bounds are often equivalent to the Theta notation.

  • 2
    $\begingroup$ I don't understand your question. What do you mean by the bound "becoming" $O(\log n)$? You've observed that inserting an item into a binary search tree can take $O(n)$ steps so what does it mean for the bound to become something else? And I don't know what you mean by "tighter bounds are often equivalent to the Theta notation". Bounds are bounds; theta notation is notation. How can a bound (a mathematical object) be equivalent to some piece of notation (a squiggle on a piece of paper)? $\endgroup$ – David Richerby Aug 18 '14 at 18:35
  • $\begingroup$ what i meant is,Is the bound loose? can we do better? $\endgroup$ – Denson Aug 19 '14 at 5:15
  • $\begingroup$ more specifically i am not sure how the notations work is the worst case scenario of an algorithm mostrly represented using the big Oh.(rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation) A good reference would be appreciated $\endgroup$ – Denson Aug 19 '14 at 5:32
  • $\begingroup$ See this question for information on what the various notation means. $\endgroup$ – David Richerby Aug 19 '14 at 9:33
  • $\begingroup$ @DavidRicherby now I understand what you were trying to say and how ridiculous this question is. Thanks for your help anyways! :) $\endgroup$ – Denson Jan 25 '17 at 10:17

For a binary search tree of $n$ nodes ,

Maximum height $=h_{max}=n-1 = \Theta (n) =O(n)$

which happens in the case of skewed binary search tree as below if all elements of a binary search are either right-skewed or left-skewed

So in worse case , to add a new node in to an existing skewed binary search tree , it takes $n$ comparisons (comparison at each level).

So, time taken $= h_{max}+1=n=\Theta\ O(n)$

Minimum height = $h_{min}=\lceil \log_2{(n+1)}\rceil-1=\Theta(\log(n))=O(\log(n))$

which happens in the case of complete binary search tree as below if all levels contains all elements except last level (Last level may be not contain all elements).

Now, number of comparisons $= h_{min}+1=\lceil \log_2{(n+1)}\rceil=\Theta(\log(n))=\ O(\log_2(n))$

Which may be the tightest upper bound you are asking for .

So, you can use either $\Theta$ or $\ O$ notation here. $\Theta$ is tighter .

Whenever you use $\Theta$ you can replace it with $\ O$ but not viceversa .

| cite | improve this answer | |

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