# 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

2. ### Richard HeathfieldGuest

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

3. ### Guest

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