Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# bst trees- running time

yotam laor
Greenhorn
Posts: 6
Hi there,

I have a pseudo- code:

now I have to prove it's running time is THETA(n),
but as far as I know it is O(nlogn), because running time of SUCCESSOR(x) is O(logn).

what am I missing here?

Thanks!

Winston Gutkowski
Bartender
Posts: 10527
64
yotam laor wrote:now I have to prove it's running time is THETA(n),
but as far as I know it is O(nlogn), because running time of SUCCESSOR(x) is O(logn).
what am I missing here?

Well, if THETA(n) is in fact the same as O(nlogn), then off the top of my head, I'd say the proof that "the running time of SUCCESSOR(x) is O(logn)".

Because, once you have that, all you need to prove is that SUCCESOR() is called exactly n times (or, more likely n-1, which is basically the same thing for O-notation), and you have your answer.

So: Why does SUCCESSOR() run in O(logn) time?

Winston

Sresh Rangi
Ranch Hand
Posts: 54
5
SUCCESSOR is only logn in the worst case, but if you're calling it for every node in the tree it will average to constant time. Think about how many times each node is visited in total during a complete traversal of the tree.