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

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)