2.6k views

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?

1. $O(1)$
2. $O(\log n)$
3. $O(n)$
4. $O(n \log n)$
edited | 2.6k views
0

@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 ?

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$(x, z, k)$

1. : if $x = nil$ then return “Error”
2. : $y \leftarrow x$
3. : while true do $\{$
4. : if  $key[y] < k$
5. : then $z \leftarrow left[y]$
6. : else $z \leftarrow right[y]$
7. : if $z = nil$ break
8. : $\}$
9. : if $key[y] > k$ then $left[y] \leftarrow z$
10. : else $right[p[y]] \leftarrow z$

Time Complexity Analysis :

1. Best $Case = O(1)$ , When it is smallest/greatest element and BST contains only all greater/smaller element than inserting element respectively.
2. Avg $Case = O(\log n)$ , When it belongs between some elements .
3. Worst $Case = O(n)$ , When it is smallest/greatest element and BST contains only all smaller/greater element than inserting element respectively.
edited
+10
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
0
And tightest upper bound is asked.So, if $O(n^2)$ were there then yes it's an upper bound but not tight.

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

(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.

0
why is not answer  O(logn) ?
+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.
0
@Bikram sir,
What does the "tightest upper bound" signify here? will the answer change if the word "tightest" is removed?
+1

O(1) : to create a node

O(n) : to find place

total= O(1) + O(n) + O(1)  = O(n)

C

+2
O(n) to find place only if it is a skewed tree. If it is a balanced tree then O(logn) to find place, isn't ?
0
yes this is the case from tightest bound refers to worst case am I  correct

1
2