[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. Asymptotic notation tricks

  1. To show equality, we will first show that every element of Theta(f(n)) is in O(f(n)) intersect Omega(f(n)), and then show that the reverse holds.

    First observe that if g(n) is in O(f(n)) and Omega(f(n)), then there exist constants c, n0 and c', n'0 such that g(n) <= c f(n) when n > n0 and g(n) >= c' f(n) when n > n'0. So c' f(n) <= g(n) <= c f(n) for n > max(n0, n'0) and thus g(n) is in Theta(n).

    Now suppose g(n) is in Theta(n). Then there exist c1, c2, n0, such that c1f(n) <= g(n) <= c2f(n) for all n > n0. But then c1f(n) <= g(n) for all n > n0---implying g(n) is in Omega(f(n))---and g(n) <= c2f(n) for all n > n0---implying it is in O(f(n)) as well. QED.

  2. Let p(n) be the polynomial. We will use the preceding result that p(n) is in Theta(nk) if and only if it is in both Omega(nk) and O(nk). Clearly p(n) is in Omega(nk) because it exceeds aknk for all n. To show that it is in O(nk), argue by induction that p(n) - aknk is in O(nk-1), and then use the sum theorem from page 56 of LevitinBook to show p(n) in O(nk).

  3. The only tricky part here is remembering that na is in o(nb) if and only if the limit as n goes to infinity of na/nb is zero. But if a < b, then na/nb = na-b = n-c for a positive constant c, and so it goes to zero. (If you want to prove this formally, argue that for any epsilon, n-c < epsilon for all n > epsilon-1/c.)

  4. Now we want to show that lnan / nb goes to zero as long as b > 0. If a < 0, then the numerator goes to zero and we are done. If a = 0, then the fraction equals n-b which again goes to zero. If a > 0, consider the ratio ln n / nb/a; using L'Hôpital's rule (see Example 2 on page 57 of LevitinBook for an example of this) we have the limit as n goes to infinity of ln n / nb/a equals the limit of (1/n)/((b/a) nb/a-1) = n-b/a/(b/a), which goes to zero in the limit since -b/a < 0.

  5. This is similar to the sum theorem from LevitinBook. Expanding the definition of O(r(n)) and O(s(n)) gives f(n) <= cfr(n) for n > nf and g(n) <= cgs(n) for n > ng. So when n > max(nf, ng), f(n)g(n) <= cfcgr(n)s(n), which satisfies the criterion for membership in O(r(n)s(n)).

2. Sums

2.1. Exercise 2.3.1

All of these except the last can be done using the summation formulas on page 414 of LevitinBook.

  1. 1+3+5+7+ ... + 999 = (1+2+3+...+999) - (2+4+6+...+998) = (1+2+3+...+999) - 2(1+2+3+...+499) = 999*1000/2 - 2*499*500/2 = 999*500 - 499*500 = 500*500 = 250000. This uses the sum from 1 to n formula.
  2. 2+4+8+16+...+1024 = (2-1024*2)/(1-2) = 2046.
  3. sumi=3n+1 1 = sumi=1n+1 1 - sumi=12 1 = n+1-2 = n-1.

  4. sumi=3n+1 i = sumi=1n+1 i - sumi=12 i = (n+1)(n+2)/2 - 3.

  5. sumi=0n-1 i(i+1) = sumi=0n-1 i2 + sumi=0n-1 i = (n-1)n(2n-1)/6 + (n-1)n/2 = (n-1)n(n/3-1/6+1/2) = n(n-1)(n/3+1/3) = (n-1)n(n+1)/3.

  6. sumj=1n 3j+1 = 9 sumi=0n-1 3i = 9(3n-1)/2

  7. sumi=1n sumj=1n ij = (sumi=1n i)(sumj=1n j) = n2(n+1)2/4.

2.2. Exercise 2.3.4

  1. It computes the sum as i goes from from 1 to n of i2.

  2. The basic operation consists of squaring i and adding it to the running total.
  3. This operation is executed n times.
  4. This algorithm runs in Theta(n) time.
  5. Use the formula sumi=1n i2 = n(n+1)(2n+1)/6 to compute the solution directly in O(1) time.

2014-06-17 11:58