# 1. Solve some recurrences

- T(n) = Theta(n) by Master Theorem.
T(n) = Theta(n) by Master Theorem, since Theta(log n) = O(n

^{1-epsilon}) for any epsilon between 0 and 1.- T(n) = Theta(n log n) by Master Theorem.
T(n) = Theta(n

^{2}) by Master Theorem.T(n) = Theta(2

^{n}) by Master Theorem (2^{n}is Omega(n^{1+epsilon}) for any epsilon > 0).Using the sum expansion described in SolvingRecurrences, T(n) = Sigma

_{i=0 to n-1}2^{i}Theta(1) + 2^{n}Theta(1) = Theta(1) Sigma_{i=0 to n}2^{i}= Theta(1) (2^{n+1}- 1) = Theta(2^{n}).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}).Let's see if we can come up with a good guess by forward substitution. We have T(1) = T(0)

^{2}= 2^{2}, T(2) = T(1)^{2}= 2^{4}, T(3) = T(2)^{2}= 2^{8}, T(4) = T(3)^{2}= 2^{16}, 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^{n}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**2**(n-1))^{2}= 2**(2*2^{n-1}) = 2**(2^{n}). So the solution is T(n) = Theta(2^{2**n}).

# 2. Iron Prof

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^{2}), 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 T

_{2}(n). From the previous case we have T_{2}(n) = Theta(n^{c}) for c > 0 so T_{2}(n) = Theta(n). The recurrence for the third procedure is T_{3}(n) = 2T_{3}(n/2) + Theta(n^{k}), and we want the solution to this recurrence to be O(n). Computing log_{b}a = 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_{3}(n) = O(n) as desired. If k = 1, then the second case applies and we have T_{3}(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.