@Bhagirathi @Dhananjay So does we have to take the meaning of tightest upper bound as the worst case time complexity always and not the average ?

The Gateway to Computer Science Excellence

+25 votes

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?

- $O(1)$
- $O(\log n)$
- $O(n)$
- $O(n \log n)$

0

+37 votes

Best answer

Option (**C**) is True .

Suppose that we need to insert a node $z$ such that $k = key[z]$. Using binary search we find a nil such that replacing it by $z$ does not break the BST-property

**BST-Insert**$\bf{(x, z, k)}$

- : if $x = nil$ then return “Error”
- : $y \leftarrow x$
- : while true do $\{$
- : if $key[y] < k$
- : then $z \leftarrow left[y]$
- : else $z \leftarrow right[y]$
- : if $z = nil$ break
- : $\}$
- : if $key[y] > k$ then $left[y] \leftarrow z$
- : else $right[p[y]] \leftarrow z$

**Time Complexity Analysis :**

- Best $Case = O(1)$ , When it is smallest/greatest element and BST contains only all greater/smaller element than inserting element respectively.
- Avg $Case = O(\log n)$ , When it belongs between some elements .
- Worst $Case = O(n)$ , When it is smallest/greatest element and BST contains only all smaller/greater element than inserting element respectively.

+12

Average case complexity is $O(logn)$ only but its not much intuitive. It requires some probabilistic analysis.

http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec4/lec4.pdf

http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec4/lec4.pdf

+33 votes

Since, in worst case the tree can grow upto the height of n (skewed tree), therefore tightest upper bound is *O*(*n*)

So, answer is (C)

+15 votes

(C) O(n)

To insert an element into BST, first we need to find its place & it might take O(n) time like in the following tree:

To insert element 60 in this tree we need to traverse all the nodes.

+6

O(logn) is average case

suppose the tree is like this

10

\

20

so to insert 21 we have to go from 10 then 20 then only can insert 21 .. tht's why it takes O(n) time in Worst Case.

suppose the tree is like this

10

\

20

so to insert 21 we have to go from 10 then 20 then only can insert 21 .. tht's why it takes O(n) time in Worst Case.

52,218 questions

59,876 answers

201,073 comments

118,119 users