Complexity of inserting n numbers into a binary search tree

Question

I have got a question, and it says "calculate the tight time complexity for the process of inserting n numbers into a binary search tree". It does not denote whether this is a balanced tree or not. So, what answer can be given to such a question? If this is a balanced tree, then height is logn, and inserting n numbers take O(nlogn) time. But this is unbalanced, it may take even O(n²) time in the worst case. What does it mean to find the tight time complexity of inserting n numbers to a bst? Am i missing something? Thanks

Briarroot

Answer 1

It could be O(n^2) even if the tree is balanced.

Suppose you're adding a sorted list of numbers, all larger than the largest number in the tree. In that case, all numbers will be added to the right child of the rightmost leaf in the tree, Hence O(n^2).

For example, suppose that you add the numbers [15..115] to the following tree:

The numbers will be added as a long chain, each node having a single right hand child. For the i-th element of the list, you'll have to traverse ~i nodes, which yields O(n^2).

In general, if you'd like to keep the insertion and retrieval at O(nlogn), you need to use Self Balancing trees.

Pycnometer

I see, but i don't get why it is O(n^2) – Briarroot

I mean, this is still a worst case, does the tight time complexity mean that? So, is that Θ(n^2)? – Briarroot

Yes, it is the worst case. You could find a specific scenario with O(nlogn). – Pycnometer

I think it's 1+2+3+4+5+...+n. – Pycnometer

One caveat - sometimes "balanced" is used in place of "dynamically balanced" or "self-balancing", which might obviously lead to confusion. – Methinks

Why would it result in O(n^2) on a balanced-BST? – Elmira

Why does the wikipedia say the worst case is O(n) for BST Insertion? en.wikipedia.org/wiki/Binary_search_tree – Linnlinnaeus

For people confused between O(n) and O(n^2): O(n) is the worst case time complexity for inserting one element in a binary search tree (explained on wikipedia). O(n^2) is the worst case time complexity for inserting n elements in a binary search tree (the original question). – Wampum

Answer 2

What wiki is saying is correct. Since the given tree is a BST, so one need not to search through entire tree, just comparing the element to be inserted with roots of tree/subtree will get the appropriate node for th element. This takes O(log2n). Once we have such a node we can insert the key there bht after that it is required push all the elements in the right aub-tree to right, so that BST's searching property does not get violated. If the place to be inserted comes to be the very last last one, we need to worry for the second procedure. If note this procedure may take O(n), worst case!. So the overall worst case complexity of inserting an element in a BST would be O(n). Thanks!

Inclose