multiplicative rule for asymptotic running times

[john.casey]

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]

(e-mail address 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.

 

[john.casey]

thanks for the reply richard.

(e-mail address removed) said:


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


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)