Description
-
Order the following list of functions by their big-Oh notation. Group together (for example, by underlining) those functions that are big-Theta of one another. (No proof needed)
Note: log = log& unless otherwise stated.
-
6 log0
2)**
log log
log&
2+,- .
2(& )
*.*)
1
4 5 &
3 *.7
5
2 log&
2.
log9
4.
5
& log
4+,- .
log
Hint: When in doubt about two functions ( ) and ( ), consider log ( ) and log ( ) or 2<(.) and 2=(.). Also, CLRS section 3.2 is very useful here.
-
Prove that if ( ) = ( ( )) and ( ) = ( ( )), then the product ( ) ( ) = ( ( ) ( )).
-
Show that logA ( ) = Q
log& 
if > 1 is a constant. -
Consider the Algorithm ArrayFind, given below, which searches an array for an element . Input: An element and an -element array, [0, . . , − 1]. (Indices start from 0.)
Output: The index such that = [ ] or −1 if no element of is equal to .
ArrayFind( , )
-
= 0
-
while < do
-
if == [ ]
-
return
-
else
-
= + 1
-
return −1
Counting assignments, comparisons, and returns only, calculate the worst-case and best-case running times of ArrayFind. (Do not use asymptotic notations or parametric constants for this;
count the exact number of these three simple operations.)
