multiplicative rule for asymptotic running times

Discussion in 'C Programming' started by john.casey@gmail.com, Oct 12, 2006.

  1. Guest

    Hi All,

    in the average case search operations on binary trees take O(log N)
    time. So what I want to know is if I am searching for multiple items
    does then mean the total search operation will take O(m log n) time
    where is the number of items I am looking for? This seems to be
    reasonably intuitive but I can't find any formal documentation in my
    old data structures book. Any ideas? thanks in advance.
     
    , Oct 12, 2006
    #1
    1. Advertising

  2. said:

    > Hi All,
    >
    > in the average case search operations on binary trees take O(log N)
    > time.


    Well, big-O is for worst-case. Assuming the tree is perfectly balanced,
    O(log N) is indeed worst-case for BSTs.

    > So what I want to know is if I am searching for multiple items
    > does then mean the total search operation will take O(m log n) time
    > where is the number of items I am looking for?


    Yes, that's the worst case. See Knuth's TAOCP 1 ("Fundamental Algorithms")
    1.2.11.1.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Oct 12, 2006
    #2
    1. Advertising

  3. Guest

    thanks for the reply richard.

    Richard Heathfield wrote:

    > said:
    >
    > > Hi All,
    > >
    > > in the average case search operations on binary trees take O(log N)
    > > time.

    >
    > Well, big-O is for worst-case. Assuming the tree is perfectly balanced,
    > O(log N) is indeed worst-case for BSTs.
    >
    > > So what I want to know is if I am searching for multiple items
    > > does then mean the total search operation will take O(m log n) time
    > > where is the number of items I am looking for?

    >
    > Yes, that's the worst case. See Knuth's TAOCP 1 ("Fundamental Algorithms")
    > 1.2.11.1.
    >
    > --
    > Richard Heathfield
    > "Usenet is a strange place" - dmr 29/7/1999
    > http://www.cpax.org.uk
    > email: rjh at above domain (but drop the www, obviously)
     
    , Oct 17, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?bWF2cmlja18xMDE=?=

    SetAuthCookie works some times and fails some times?

    =?Utf-8?B?bWF2cmlja18xMDE=?=, Mar 23, 2006, in forum: ASP .Net
    Replies:
    0
    Views:
    528
    =?Utf-8?B?bWF2cmlja18xMDE=?=
    Mar 23, 2006
  2. =?Utf-8?B?bWF2cmlja18xMDE=?=

    Forms Authentication Fails some times and not some times???

    =?Utf-8?B?bWF2cmlja18xMDE=?=, Mar 28, 2006, in forum: ASP .Net
    Replies:
    0
    Views:
    501
    =?Utf-8?B?bWF2cmlja18xMDE=?=
    Mar 28, 2006
  3. djskrill
    Replies:
    9
    Views:
    707
    djskrill
    Oct 1, 2003
  4. Replies:
    0
    Views:
    1,391
  5. Eric Jonas

    cPickle asymptotic performance?

    Eric Jonas, Jun 12, 2008, in forum: Python
    Replies:
    3
    Views:
    319
    Hrvoje Niksic
    Jun 13, 2008
Loading...

Share This Page