Homework 6 (assigned July 27, due August 2)

Reading: Rosen chapter 2, section 2.4; chapter 3, sections 3.1–3.3.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. Use the definitions of Big Oh, Ω, Θ, and little Oh to determine if the following assertions are true or false.
   • n(n + 1)/2 = O(n³)
   • n(n + 1)/2 = O(n²)
   • n(n + 1)/2 = Θ(n³)
   • n(n + 1)/2 = Ω(n)
   • n(n + 1)/2 = o(n³)
   • n(n + 1)/2 = o(n²)

2. Prove the following rules using the definitions of the notations involved.
   • If f₁(n) = O(g₁(n)) and f₂(n) = O(g₂(n)), then f₁(n) + f₂(n) = O(max{|g₁(n)|, |g₂(n)|}).
   • If f₁(n) = Ω(g₁(n)) and f₂(n) = Ω(g₂(n)), then f₁(n) + f₂(n) = Ω(max{|g₁(n)|, |g₂(n)|}).
   • If f₁(n) = Θ(g₁(n)) and f₂(n) = Θ(g₂(n)), then f₁(n) + f₂(n) = Θ(max{|g₁(n)|, |g₂(n)|}).
   What does the last rule imply for an algorithm that comprises two consecutively executed parts?

3. For each of the following pairs of functions f (n) and g(n) below, indicate whether f (n) is O, o, Ω, or Θ of g(n). Note that zero, one, or more than one of these relations may hold for a given pair; list all the correct ones.
   1. f (n) = n¹⁰⁰;   g(n) = 2ⁿ.
   2. f (n) = n^lg n;   g(n) = (lg n)ⁿ.

4. Use summation facts and known closed forms to transform the following summation into a closed form. Note: lower and upper limits of summation are subscripted to the sum symbol.
   ∑_{1 ≤ k ≤n} k³.
   Use the method shown in class, starting with the difference between two successive general terms of the sum. See also exercises 19 and 21 of section 2.4, page 162 of Rosen.

Assigned problems (to be handed in):

1. Prove each of the following statements. (5 points each)
   1. log₂(kn) = Θ(log₂n), where k is a real number > 0.
   2. log₂(k + n) = Θ(log₂n), where k is a real number > 0.
   3. (n + a)^b = Θ(n^b) for all real constants a and b such that b > 0.

2. Prove each of the following statements. (5 points each)
   1. n³ = o(2ⁿ).
      (Hint: Use l'Hopital's rule repeatedly until n disappears from the numerator.)
      (Note: The more general result, n^b = o(aⁿ) for all real constants a and b such that a > 1, is also true.)
   2. (log₂n)^a = o(n^a), for any real constant a > 0.
      (Note: The more general result, (log₂n)^b = o(n^a) for any real constants a and b with a > 0, is also true.)

3. Find two functions f (n) and g(n) that satisfy the following relationship. If no such f  and g exist, explain why not. (5 points each)
   1. f (n) = o(g(n)) and f (n) ≠ Θ(g(n))
   2. f (n) = Θ(g(n)) and f (n) = o(g(n))
   3. f (n) = Θ(g(n)) and f (n) ≠ O(g(n))
   4. f (n) = Ω(g(n)) and f (n) ≠ O(g(n))

4. For each of the following pairs of functions f (n) and g(n) below, indicate whether f (n) is O, o, Ω, or Θ of g(n). Note that zero, one, or more than one of these relations may hold for a given pair; list all the correct ones and prove your answers. Note: lg n = log₂ n. (5 points each)
   1. f (n) = n^1/3,   g(n) = n^2/3.
   2. f (n) = (lg n)¹²;   g(n) = √n.
   3. f (n) = n2ⁿ;   g(n) = 3ⁿ.

5. Compute each of the following sums and give Θ-estimates for each. Note: lower and upper limits of summation are subscripted to the sum symbol. (5 points each)
   1. ∑_{0 ≤ i ≤ n − 1} i(i + 1)
   2. ∑_{1 ≤ j ≤ n} 3^j+1
   3. ∑_{1 ≤ i ≤ n} ∑_{1 ≤ j ≤ n} ij

6. Prove: If c is a positive real number, then g(n) = ∑_{0 ≤ k ≤ n} c^k = 1 + c + c² + … + cⁿ is:
   1. Θ(1) if c < 1.
   2. Θ(n) if c = 1.
   3. Θ(cⁿ) if c > 1.
   (5 points each)

7. Find a closed form for the sum
   ∑_{1 ≤ k ≤ n} k2^k = 1 × 2 + 2 × 2² + 3 × 2³ + … + n2ⁿ
   using summation facts and known closed forms. (10 points)
   (Hint: Use the method shown in class, starting with the difference between two successive general terms of the sum. See "Do" exercise 4 above, and exercises 19 and 21 of section 2.4, page 162 of Rosen.)