Homework 3
Document last modified: 

1. Exercise 3.1-1 - The following is half the proof.

   Prove max(f(n), g(n)) is Q(f(n) + g(n))

   That means determine two constants c₁ and c₂ such that:

   c₁(f(n) + g(n)) ≤ max(f(n), g(n)) ≤ c₂(f(n) + g(n))

   To clarify max(f(n), g(n)) function, define a function h(n) = max(f(n), g(n)):

              æ f(n) if (fn) ³ g(n)
   h(n) =  í
              è g(n) if f(n) < g(n)

   Need to find:c₁ and c₂

   c₂:  To prove max(f(n), g(n)) ≤ c₂(f(n) + g(n))

   Since f (n) and g(n) are asymptotically nonnegative, there exists f(n) ≥ 0 and g(n) ≥ 0 for all n ≥ n₀.

   Thus for n ≥ n0:

   f(n)+g(n)≥f(n)≥0

   f(n)+g(n)≥g(n)≥ 0

   Since for any particular n, h(n) = max(f(n), g(n)) is either f(n) or g(n)

   0 ≤  h(n) = max(f(n), g(n)) ≤ c₂(f(n) + g(n)) for all n ≥ n₀

   holds for c₂=1 in definition of Q.

   c₁:  To prove c₁(f(n) + g(n)) ≤ max(f(n), g(n)) = h(n)

    

2. Exercise 3.1-4  (Ignore this problem, already completed in Exercise 3).

   Is 2ⁿ⁺¹ = O(2ⁿ)?

   To solve, try to determine one constant c such that:

   2ⁿ⁺¹ ≤ c2ⁿ

   If you can find that constant c, then answer true, but if c turns out to not be constant, i.e., it depends on n (which isn’t constant), then it’s false.

    

3. Find and prove the closed-end equation for:

   T(1) = 1              

   T(n) = T(n/3) + 1  for n>1

   Hint: Use backward substitution.

    

4. Problem 3-1a

   

   Where a_d>0, and k a constant.

   If k ³ d, then  p(n) = O(n^k)

   Must determine c and n₀ such that p(n) ≤ cn^k for n > n₀

   Expand out p(n), the summation, in the inequality, do some algebra to simplify and then let n go to infinity for k=d and k>d.

    

5. Problem 3-4b

Show the conjecture is false: f(n)+g(n) = Q( min( f(n), g(n) ) )

Hint: Give an example that contradicts: f(n)+g(n) = Q( min( f(n), g(n) ) )

Turn in

1. Cover sheet with your name, C455, date, and Homework 3.
2. Typed or neatly handwritten answers.