The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.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)$
asked in DS by Veteran (342k points)
edited by | 1.6k views

4 Answers

+28 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$(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.


 

answered by Boss (14.1k points)
edited by
+6
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
+22 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)

 

answered by Active (1.1k points)
+10 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.

answered by (235 points)
0
why is not answer  O(logn) ?
+5
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?
+3 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

answered by Active (4.3k points)
+1
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 ?


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,506 questions
42,827 answers
121,678 comments
42,181 users