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, n₀ and c', n'₀ such that g(n) <= c f(n) when n > n₀ and g(n) >= c' f(n) when n > n'₀. So c' f(n) <= g(n) <= c f(n) for n > max(n₀, n'₀) and thus g(n) is in Theta(n).

   Now suppose g(n) is in Theta(n). Then there exist c₁, c₂, n₀, such that c₁f(n) <= g(n) <= c₂f(n) for all n > n₀. But then c₁f(n) <= g(n) for all n > n₀---implying g(n) is in Omega(f(n))---and g(n) <= c₂f(n) for all n > n₀---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(n^k) if and only if it is in both Omega(n^k) and O(n^k). Clearly p(n) is in Omega(n^k) because it exceeds a_kn^k for all n. To show that it is in O(n^k), argue by induction that p(n) - a_kn^k is in O(n^k-1), and then use the sum theorem from page 56 of LevitinBook to show p(n) in O(n^k).

3. The only tricky part here is remembering that n^a is in o(n^b) if and only if the limit as n goes to infinity of n^a/n^b is zero. But if a < b, then n^a/n^b = n^a-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 ln^an / n^b 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 / n^b/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 / n^b/a equals the limit of (1/n)/((b/a) n^b/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) <= c_fr(n) for n > n_f and g(n) <= c_gs(n) for n > n_g. So when n > max(n_f, n_g), f(n)g(n) <= c_fc_gr(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. sum_i=3ⁿ⁺¹ 1 = sum_i=1ⁿ⁺¹ 1 - sum_i=1² 1 = n+1-2 = n-1.

4. sum_i=3ⁿ⁺¹ i = sum_i=1ⁿ⁺¹ i - sum_i=1² i = (n+1)(n+2)/2 - 3.

5. sum_i=0^n-1 i(i+1) = sum_i=0^n-1 i² + sum_i=0^n-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. sum_j=1ⁿ 3^j+1 = 9 sum_i=0^n-1 3ⁱ = 9(3ⁿ-1)/2

7. sum_i=1ⁿ sum_j=1ⁿ ij = (sum_i=1ⁿ i)(sum_j=1ⁿ j) = n²(n+1)²/4.

2.2. Exercise 2.3.4

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

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 sum_i=1ⁿ i² = n(n+1)(2n+1)/6 to compute the solution directly in O(1) time.