CODEWITHSUNDEEP
algorithmtime-complexitybinary-search-tree
Mahajna
Mahajna

Reputation: 111

The time complexity of doing O(h) algorithm n times

What is the time complexity of doing O(h) algorithm when h is the height of the node in BST n times (the number of elements in the tree) , I believe it's O(n) and not O(n*h) but I have no clue how to prove it.

The specific algorithm that works in O(h) is finding the In-order predecessor of an element in BST.

Upvotes: 3

Views: 304

Answers (2)

templatetypedef
templatetypedef

Reputation: 373422

The cost of computing inorder successors n times in any BST is O(n). To see this, count how many times you touch each edge in the tree. You’ll pass down the edge once when you first explore a subtree, and once more after you leave it. Overall, this means you touch each edge at most twice, so the total work done is O(n).

Note that generally speaking you can upper-bound the cost of performing n O(h)-time on a BST that has height h at O(hn), and that will never underestimate things. However, if you know more specifically about the algorithm you’re using, as in this case, you can get a tighter bound.

Upvotes: 2

Daniel
Daniel

Reputation: 7724

O(n²).

A binary search tree is not balanced, which means that the height of a node can be equal to the number of nodes of the tree, hence O(n²).

Upvotes: 1

Related Questions