CODEWITHSUNDEEP
data-structuresrandombig-obinary-search-treetime-complexity
FlowerFire
FlowerFire

Reputation: 81

Running time complexity for binary search tree

I already know if you try to find the item with particular key the running time of worst case is O(n) ,nis the number of node. If you try to print out all the data items in order of their keys then the running time of worst case is O(n). If you try to search for a particular data item(you don't know the key) then the running time of worst case is O(n). However, what if the keys and data are both integers and, the input items were randomly scrambled before they were inserted. Will the worst cases of running time still the same?

Upvotes: 1

Views: 17353

Answers (2)

templatetypedef
templatetypedef

Reputation: 372814

In the worst-case, yes. A randomly-built BST with n nodes has a 2n-1 / n! chance of being built degenerately, which is extremely rare as n gets to any reasonable size but still possible. In that case, a lookup might take Θ(n) time because the search might need to descend all the way down to the deepest leaf.

On expectation, though, the tree height will be Θ(log n), so lookups will take expected O(log n) time.

The time to print a tree is independent of the shape of the tree, by the way. It's always Θ(n).

Hope this helps!

Upvotes: 5

Sumit
Sumit

Reputation: 726

You might not be able to change the worst case running time of a normal BST, however, if you randomize the input(in less than O(log n) time, if you're targeting O(log n) overall), then chances of that worst case occurring are highly rare. See mathematical analysis here.

In case you are interested in guaranteed O(log n) time, you can use Balanced BSTs like Red Black Trees etc. However, time to print will still be O(n) as you still need to visit each and every node before you can print it.

Upvotes: 2

Related Questions