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?

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) — Jon Kiparsky
– Jon Kiparsky, Commented Oct 16, 2014 at 21:14
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. — arunmoezhi
– arunmoezhi, Commented Oct 17, 2014 at 3:25

Paco · Accepted Answer · 2017-07-29 15:33:47Z

5

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)

answered Jul 29, 2017 at 15:33

Paco

511 silver badge2 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time Complexity of a Binary Search Tree Insert method

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related