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?
@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)$
Time Complexity Analysis :
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)
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.
O(1) : to create a node
O(n) : to find place
O(1) : to link
total= O(1) + O(n) + O(1) = O(n)