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

---

The correct answer is C. O(n).

---

Why?

To insert a value into a Binary Search Tree, you must traverse from the root to the correct leaf position.

The time taken is proportional to the height of the tree:

O(h)

where h is the height.

---

Best Case (Balanced BST)

If the BST is balanced:

h=O(log⁡n)

Insertion takes O(log n).

---

Worst Case (Skewed BST)

If the BST is completely skewed (like a linked list):

1
 \
  2
   \
    3
     \
      ...

Then:

h=O(n)

Insertion takes O(n).

---

Meaning of “Tightest Upper Bound”

The question does not assume the BST is balanced.

So we must consider the worst case over all possible BST shapes.

Thus the tightest upper bound is:

O(n)

---

Final Answer

C. O(n)

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

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

---

Thank you sir now I very well understood the meaning of it.I also had the same confusion.

---

@Sachin Mittal 1 Very helpful.

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

Answer 5

Ans : (C)

It's a very common trap when it comes to BST , We always think BST as a Balanced BST in first view .
But when asked about worst case always go for Skewed BST.

There for :

Worst case time in : Searching -> O(n) , Inserting ->O(n) , Deleting -> O(n)

Answer 6

## Answer

The tightest upper bound for the time complexity of inserting an object into a binary search tree (BST) of  nodes is **** (Option C).

---

### Explanation

The time complexity of inserting a node into a Binary Search Tree is directly proportional to the **height** of the tree, as the algorithm must traverse from the root to a leaf position to find the correct insertion point.

* **Average Case:** In a randomly built or balanced BST, the height is , leading to a complexity of .
* **Worst Case (Skewed Tree):** In the worst-case scenario, the BST can become **skewed** (left or right). This occurs when elements are inserted in a strictly increasing or decreasing order. In a skewed tree, the height is , and the structure effectively behaves like a linked list.
* **Insertion Logic:** To insert a new element in a skewed tree, you might have to compare it with every single node in the tree to reach the bottom-most leaf.
* Number of comparisons =
* Time Complexity =

Since the term **"tightest upper bound"** refers to the most restrictive Big-O notation that still accounts for the worst-case scenario,  is the correct answer.