Velocity Reviews > multiplicative rule for asymptotic running times

# multiplicative rule for asymptotic running times

john.casey@gmail.com
Guest
Posts: n/a

 10-12-2006
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.

Richard Heathfield
Guest
Posts: n/a

 10-12-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) 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)

john.casey@gmail.com
Guest
Posts: n/a

 10-16-2006
thanks for the reply richard.

Richard Heathfield wrote:

> (E-Mail Removed) 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)

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Eric Jonas Python 3 06-13-2008 06:38 AM shailajabtech@gmail.com Java 0 10-12-2006 08:36 AM Tacky Software 0 10-02-2006 01:52 AM =?Utf-8?B?bWF2cmlja18xMDE=?= ASP .Net 0 03-28-2006 10:48 PM =?Utf-8?B?bWF2cmlja18xMDE=?= ASP .Net 0 03-23-2006 09:24 PM

Advertisments