Chapter 1: Homework 1

1. (10 points) Exercise 9.2c of Aho, Hopcroft, and Ullman. "Solve" means "guess a solution and prove it is correct using induction." Assume that n is a power of 2.
   c) T(n) = 8 T(n/2) + n³
   Note the hint: The solution contains a term cn³log₂n

2. (10 points) Exercise 9.10c of Aho, Hopcroft, and Ullman.
   Find a close-form expression for the sum of 2ⁱ, for i=0 up to n. Prove by induction that your expression is correct.

3. (5 points) Sort the following functions into increasing order of magnitude.
   • n²
   • n log n
   • n^-1
   • n/ log n
   • 2^log₂n

4. (15 points) Exercises 8 a, b, c pg. 51 Howowitz, Sahni, Rajasekaran
   8. Show that the following inequalities are correct:
   • (a) 5n² - 6n = (n²)
   • (b) n! = O(nⁿ)
   • (c) 2n²2ⁿ + nlogn = (n²2ⁿ)

5. (10 points) Exercises 9 a, b pg. 52 Howowitz, Sahni, Rajasekaran
   9. Show that the following inequalities are incorrect:
   • (a) 10n² + 9 = O(n)
   • (b) n²logn = (n²)

Note that for proving inequalities do not hold, it is not sufficient simply to find specific c's and n's that do not work since I may be able to find a c or n that does. Hence, you need to show that sooner or later any choice of c will have a problem. This is usually done by considering the fact that the statement must be true "for all n, n > n₀"
Specifically, that n approaches infinity.