[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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(n1-epsilon) for any epsilon between 0 and 1.

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

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

  6. 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).

  7. 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).

  8. 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

  1. T(n) = T(n-1) + Theta(n); expand this as T(n) = Sigmai=1 to n Theta(i) + T(0) = Theta(n2).

  2. 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.

  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 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.

2014-06-17 11:58