This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Beginning Java and the fly likes bst trees- running time Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "bst trees- running time" Watch "bst trees- running time" New topic
Author

bst trees- running time

yotam laor
Greenhorn

Joined: May 02, 2014
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

Joined: Mar 17, 2011
Posts: 7549
    
  18

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

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Sresh Rangi
Ranch Hand

Joined: Nov 28, 2012
Posts: 45
    
    1
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.
 
jQuery in Action, 2nd edition
 
subject: bst trees- running time
 
Similar Threads
How the remove operation in LinkedList is of O(1) time complexity?
How to get System Timezone?
Loop With Switch
Linked List - inserting value to correct position
Tomcat madness!