# bst trees- running time

yotam laor

Greenhorn

Posts: 6

posted 1 year ago

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

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

Winston

- 0

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

I wonder how a hamster feels, out in the wild where there's no wheels -- Ogden Nash (or should've been).

Articles by Winston can be found here

I agree. Here's the link: http://aspose.com/file-tools |