Time Complexity of a Binary Search Tree Insert method

Question

Good day!

I have a question regarding the time complexity of a binary search tree insertion method. I read some of the answers regarding this but some were different from each other. Is the time complexity for a binary search tree insertion method O(log n) at average case and O(n) at worst case? Or is it O(n log n) for the average case and O(n^2) for the worst case? When does it become O(n log n) at average case and O(n^2) at worst case?

Solution

In avg case, is O(log n) for 1 insert operation since it consists of a test (constant time) and a recursive call (with half of the total number of nodes in the tree to visit), making the problem smaller in constant time. Thus for n insert operations, avg case is O(nlogn). The key is that the operation requieres time proportional to the height of the tree. In average, 1 insert operation is O(logn) but in the worst case the height is O(n) If you're doing n operations, then avg is O(nlgn) and worst O(n^2)

Comments

[dramzy]

stackoverflow.com/questions/15322386/…

[Boris the Spider]

Try reading the Wikipedia article.

[Jon Kiparsky]

For a basic binary tree, insert is O(log n) if the tree is balanced and degrades to O(n) if the tree is maximally unbalanced (ie, a linked list)

[arunmoezhi]

for 1 insert operation, avg case is O(lgn) and worst case is O(n). For n insert operations, avg case is O(nlgn) and worst case is O(n^2). But usually people refer to complexity of 1 insert operation.