Homework 5 (assigned July 21, due July 26)

Reading: Rosen 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. The following are two useful rules for computing asymptotic bounds on algebraic combinations of functions. Assume that all functions are nonnegative and real-valued.
   1. If f₁(n) = Θ(g₁(n)) and f₂(n) = Θ(g₂(n)), then f₁(n) + f₂(n) = Θ(max{g₁(n), g₂(n)}).
   2. If f₁(n) = Θ(g₁(n)) and f₂(n) = Θ(g₂(n)), then f₁(n) ⋅ f₂(n) = Θ(g₁(n) ⋅ g₂(n)).
   Use the above rules to derive Θ-estimates for the following expressions.
   • (3n + 1)²
   • (6n + 4)(1 + log₂n)
   • (n³ − 3n² + 2)(log₂n − 1) + (17 log₂n + 19)(n³ − 2)

2. True or false? Prove your answer.
   • If f (n) = Θ(g(n)), then 2^f (n) = Θ(2^g(n)).
   • If f (n) = Θ(g(n)), then log₂ f (n) = Θ(log₂ g(n)).
   • If f₁(n) = Θ(g₁(n)) and f₂(n) = Θ(g₂(n)), then f₁(n) − f₂(n) = Θ(g₁(n) − g₂(n)).

3. For each of the following questions, answer yes or no and briefly explain your answer.
   • If I prove that an algorithm takes O(n²) worst-case time, is it possible that it takes O(n) on all inputs?
   • If I prove that an algorithm takes Θ(n²) worst-case time, is it possible that it takes O(n) on some inputs?
   • If I prove that an algorithm takes Θ(n²) worst-case time, is it possible that it takes O(n) on all inputs?

4. Given finite sets A and B, consider a function f : A → B.
   • When f  is injective, what is implied about the sizes of A and B?
   • When f  is surjective, what is implied about the sizes of A and B?
   • Prove that if A and B are finite and f : A → B and g : B → A are injections, then |A| = |B| and f  and g are bijections.

Assigned problems (to be handed in):

1. Suppose you have algorithms with the five running times listed below. Assume these are the exact number of operations performed as a function of the input size n. You have a computer that can perform 10¹⁰ operations per second, and you need to compute a result in at most 1 hour of computation. For each of the algorithms, what is the largest input size n for which you would be able to get the result within 1 hour? (2 points each)
   1. n³
   2. 100n²
   3. n log₂n
   4. 2ⁿ
   5. 2²ⁿ

2. True or false? Prove your answer using the definition of Big Oh. (5 points each)
   1. 2²ⁿ = O(2ⁿ).
   2. log₂ 3ⁿ = O(log₂ 2ⁿ).

3. For each of the following pairs of functions f (n) and g(n), give an appropriate positive constant c such that |f (n)| ≤  c ⋅ |g(n)| for all n ≥ 1. (3 points each)
   1. f (n) = 3n² + 2n log₂ n + 1,   g(n) = 2n².
   2. f (n) = n ⋅ √n  + n²,   g(n) = n².
   3. f (n) = n² − n + 1,   g(n) = n²/2.

4. For each of the following pairs of functions, either f (n) = O(g(n)), f (n) = Ω(g(n)), or f (n) = Θ(g(n)). Determine which relationship is correct and prove your answer. Note: log = log₂ throughout. (5 points each)
   1. f (n) = log n²;   g(n) = log n + 5.
   2. f (n) = log²n, where log²n = (log n) × (log n);   g(n) = log n.
   3. f (n) = n log n + n;   g(n) = log n.
   4. f (n) = 10;   g(n) = log 10.
   5. f (n) = 4n log n + n;   g(n) = (n² − n)/2.

5. Find positive and nondecreasing functions f (n) and g(n) defined for all positive integers such that neither f (n) = O(g(n)) nor g(n) = O(f (n)) holds. (10 points)

6. Find the flaw in the following proof that any algorithm has a run time that is O(n). (10 points)
   To prove: We must show that the time required for an input of size n is at most a constant times n.
   Proof. By induction on n.
   Base case. Suppose that n = 1. If the algorithm takes c units of time for an input of size 1, the algorithm takes at most c ⋅ 1 units of time. Thus the assertion is true for n = 1.
   Inductive step. Assume that the time required for an input of size n is at most c′n and that the time for processing an additional item is c′′. Then the total time required for an input of size n + 1 is at most
   c′n + c′′ ≤ cn + c = c(n + 1).
   The inductive step has been verified.
   By induction, for input of size n, the time required is at most a constant time n. Therefore, the run time is O(n).