edited by
12,116 views
41 votes
41 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?

  1. $O(1)$
  2. $O(\log n)$
  3. $O(n)$
  4. $O(n \log n)$
edited by

4 Answers

Best answer
51 votes
51 votes

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

  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 by
42 votes
42 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)

18 votes
18 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:

Skewed Tree

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

4 votes
4 votes

O(1) : to create a node

O(n) : to find place

O(1) : to link

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

C

Answer:

Related questions

27 votes
27 votes
2 answers
1
52 votes
52 votes
9 answers
3