1. Solve some recurrences

1. T(n) = Theta(n) by Master Theorem.

2. T(n) = Theta(n) by Master Theorem, since Theta(log n) = O(n^1-epsilon) for any epsilon between 0 and 1.

3. T(n) = Theta(n log n) by Master Theorem.

4. T(n) = Theta(n²) by Master Theorem.

5. T(n) = Theta(2ⁿ) by Master Theorem (2ⁿ is Omega(n^1+epsilon) for any epsilon > 0).

6. Using the sum expansion described in SolvingRecurrences, T(n) = Sigma_{i=0 to n-1} 2ⁱ Theta(1) + 2ⁿ Theta(1) = Theta(1) Sigma_{i=0 to n} 2ⁱ = Theta(1) (2ⁿ⁺¹ - 1) = Theta(2ⁿ).

7. Expanding this into the corresponding sum gives T(n) = Sigma_{i=1 to n} Theta(i^1/2) + T(0). Using either the integral trick or looking at large terms (e.g. Sigma_{i=n/2 to n} i^1/2), we can compute that Sigma_{i=1 to n}i^1/2 is Theta(n^3/2), which implies that T(n) = Theta(n^3/2).

8. Let's see if we can come up with a good guess by forward substitution. We have T(1) = T(0)² = 2², T(2) = T(1)² = 2⁴, T(3) = T(2)² = 2⁸, T(4) = T(3)² = 2¹⁶, etc. The exponents are doubling at each step, so we can guess T(n) = 2^2**n (where I am writing the Fortran-style 2**n for 2ⁿ to get around the no-double-superscript limitation in MoinMoin). To verify the guess, observe that T(0) = 2 = 2^2**0 and T(n) = T(n-1)² = (2**2**(n-1))² = 2**(2*2^n-1) = 2**(2ⁿ). So the solution is T(n) = Theta(2^2**n).

2. Iron Prof

1. T(n) = T(n-1) + Theta(n); expand this as T(n) = Sigma_{i=1 to n} Theta(i) + T(0) = Theta(n²).

2. T(n) = T(n/2) + Theta(n^c). The default solution for the Master Theorem is T(n) = Theta(n^{lg 1}) = Theta(1). So if c > 0 where are in case 3 where T(n) = Theta(n^c). Since the previous procedure ran in time Theta(n²), the new procedure is at least as fast as long as c <= 2.

3. First we have to compute the number of lectures for the second procedure with c = 1. To avoid confusion let's call this number T₂(n). From the previous case we have T₂(n) = Theta(n^c) for c > 0 so T₂(n) = Theta(n). The recurrence for the third procedure is T₃(n) = 2T₃(n/2) + Theta(n^k), and we want the solution to this recurrence to be O(n). Computing log_ba = lg 2 = 1 for the Master Theorem gives a default solution of Theta(n). If k < 1, the first case of the theorem applies and we have T₃(n) = O(n) as desired. If k = 1, then the second case applies and we have T₃(n) = Theta(n log n), which is too big. If k > 1, then T_3(n) = Theta(n^k) = omega(n), which is much too big. It follows that procedure three is only faster than procedure two if k is strictly less than 1.