1. Solve some recurrences
- T(n) = Theta(n) by Master Theorem.
T(n) = Theta(n) by Master Theorem, since Theta(log n) = O(n1-epsilon) for any epsilon between 0 and 1.
- T(n) = Theta(n log n) by Master Theorem.
T(n) = Theta(n2) by Master Theorem.
T(n) = Theta(2n) by Master Theorem (2n is Omega(n1+epsilon) for any epsilon > 0).
Using the sum expansion described in SolvingRecurrences, T(n) = Sigmai=0 to n-1 2i Theta(1) + 2n Theta(1) = Theta(1) Sigmai=0 to n 2i = Theta(1) (2n+1 - 1) = Theta(2n).
Expanding this into the corresponding sum gives T(n) = Sigmai=1 to n Theta(i1/2) + T(0). Using either the integral trick or looking at large terms (e.g. Sigmai=n/2 to n i1/2), we can compute that Sigmai=1 to ni1/2 is Theta(n3/2), which implies that T(n) = Theta(n3/2).
Let's see if we can come up with a good guess by forward substitution. We have T(1) = T(0)2 = 22, T(2) = T(1)2 = 24, T(3) = T(2)2 = 28, T(4) = T(3)2 = 216, etc. The exponents are doubling at each step, so we can guess T(n) = 22**n (where I am writing the Fortran-style 2**n for 2n to get around the no-double-superscript limitation in MoinMoin). To verify the guess, observe that T(0) = 2 = 22**0 and T(n) = T(n-1)2 = (2**2**(n-1))2 = 2**(2*2n-1) = 2**(2n). So the solution is T(n) = Theta(22**n).
2. Iron Prof
T(n) = T(n-1) + Theta(n); expand this as T(n) = Sigmai=1 to n Theta(i) + T(0) = Theta(n2).
T(n) = T(n/2) + Theta(nc). The default solution for the Master Theorem is T(n) = Theta(nlg 1) = Theta(1). So if c > 0 where are in case 3 where T(n) = Theta(nc). Since the previous procedure ran in time Theta(n2), the new procedure is at least as fast as long as c <= 2.
First we have to compute the number of lectures for the second procedure with c = 1. To avoid confusion let's call this number T2(n). From the previous case we have T2(n) = Theta(nc) for c > 0 so T2(n) = Theta(n). The recurrence for the third procedure is T3(n) = 2T3(n/2) + Theta(nk), and we want the solution to this recurrence to be O(n). Computing logba = 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 T3(n) = O(n) as desired. If k = 1, then the second case applies and we have T3(n) = Theta(n log n), which is too big. If k > 1, then T3(n) = Theta(nk) = 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.