• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

bst trees- running time

 
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Ranch Hand
Posts: 59
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic