GATE CSE 2013 | Question: 7

Question

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?

• A. $O(1)$
• B. $O(\log n)$
• C. $O(n)$
• D. $O(n \log n)$

Comments

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

---

skewed tree

Answer 1

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.

Comments

Hi @GO Classes

Is tightest upper bound and worst case time are one and the same?

If yes then should we always consider worst case time if they ask tightest upper bound time?

Kindly confirm.

Thanks,

---

@Nandhakumar

If a question asks about the time complexity of an algorithm without specifying whether it's the best, worst, or average case, it means they want to know the complexity in all scenarios.

For example, if the best case is $ \theta(n) $ and the worst case is $ \theta(n^2) $, you can say that the algorithm's time complexity is $ O(n^2) $ or $ O(n^3) $ or even $ O(n^4) $. However, if they insist on the tightest bound, then the answer would be $ O(n^2) $.

Summary:

Question (MSQ):

What is the tightest bound time complexity of an algorithm that has a best-case time complexity $ \theta(n) $ and a worst-case time complexity $ \theta(n^2) $? (Please try to solve it without looking at the answers)

A. $ \Omega(n) $

B. $ \Omega(n^2) $

C. $ O(n^2) $

D. $ O(n^3) $

The correct answers are A and C.

($ \Omega(n) $ is tighest lower bound and $ O(n^2) $ is tighest upper bound).

---

Thank you @Sachin Mittal 1sir for the quick update. Got it now.

Answer 2

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)

Answer 3

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

Comments

why is not answer  O(logn) ?

---

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.

---

@Bikram sir,
What does the "tightest upper bound" signify here? will the answer change if the word "tightest" is removed?

---

https://cs.stackexchange.com/questions/19141/what-is-an-asymptotically-tight-upper-bound

Answer 4

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

Comments

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 ?

---

yes this is the case from tightest bound refers to worst case am I  correct

---

 

 

https://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent