Due: Wednesday, May 26.
Exercise 3-2, page 58 from the text. For part (c), draw a qualitative graph of the two functions before attempting to answer the question. For part (f), use Stirling's approximation (Equation 3.19). For the purposes of this problem, the following very crude approximation is adequate.
| n! = nn |
where you should read = as "approximately equal". To answer, fill in the following table, writing yes or no in each spot.
| A | B | O | o | OMEGA | omega | THETA |
|---|---|---|---|---|---|---|
| (lg n)k | ne | |||||
| nk | cn | |||||
| n1/2 | nsin n | |||||
| 2n | 2n/2 | |||||
| nlg c | clg n | |||||
| lg(n!) | lg(nn) |
Exercise 4.3-1, page 75, all parts.