Solution to homework #2

Big-oh exercises

1. Give the definition of f(n) = O( g(n) ).

ANSWER:

f(N) = O(g(N)) means that there exist positive constants c and n₀ such that f(N) ≤ c * g(N) for all N ≥ n₀

2. Demonstrate, by applying the definition of big-oh, that
1. n² = O(n²)

   ANSWER:
   
   We must demonstrate that there exist positive constants c and n₀ such that

   n² ≤ c * n² for all n ≥ n₀

   Choose c = 1. Clearly n² ≤ n² holds for all values of n, so it certainly holds whenever n ≥ 1.

   If we choose n₀ = 1, we have demonstrated that there exist positive constants c = 1 and n₀ = 1 such that

   n² ≤ c * n² for all n ≥ n₀

2. n² + 1 = O(n²)

   ANSWER:
   
   We must demonstrate that there exist positive constants c and n₀ such that

   n² + 1 ≤ c * n² for all n ≥ n₀

   Choose c = 2. Then

   n² + 1 ≤ 1 * n²

   holds whenever

   1 ≤ 1 * n²

   which is true for all n ≥ 1.

   If we choose n₀ = 1, we have demonstrated that there exist positive constants c = 2 and n₀ = 1 such that

   n² + 1 ≤ c * n² for all n ≥ n₀

3. k * n² + 1 = O(n²), where k is a positive constant

   ANSWER:
   
   We must demonstrate that there exist positive constants c and n₀ such that

   k * n² + 1 ≤ c * n² for all n ≥ n₀

   Choose c = k + 1. Since k is a positive constant certainly k + 1 is too. Then

   k * n² + 1 ≤ (k + 1) * n²

   holds whenever

   1 ≤ 1 * n²

   which is true for all n ≥ 1.

   If we choose n₀ = 1, we have demonstrated that there exist positive constants c = k + 1 and n₀ = 1 such that

   n² + 1 ≤ c * n² for all n ≥ n₀

3. Demonstrate, by giving appropriate counterexamples, that the following claims are false:
1. If f(n) = O(g(n)) and f(n) = O(h(n)) then g(n) = h(n).

ANSWER:

A counterexample is in this case a set of assignments to f, g and h so that f(n) = O(g(n)) and f(n) = O(h(n)) are both true but g(n) ≠ h(n)

Pick f(n) = n², g(n)= n³ and h(n)= n⁴.

We can show that f(n) = O(g(n)) and f(n) = O(h(n)) are both true. However, it is clearly the case that g(n) ≠ h(n).

2. If f(n) = O(g(n)) and g(n) = O(f(n)) then f(n) = g(n).

ANSWER:

A counterexample is in this case a set of assignments to f, g and h so that f(n) = O(g(n)) and g(n) = O(f(n)) are both true but f(n) ≠ g(n)

Pick f(n) = n² and g(n)= n²+1.

We can show that f(n) = O(g(n)) and g(n) = O(f(n)) are both true. However, it is clearly the case that f(n) ≠ g(n).

4. Prove, by applying the definition of f(n) = O(g(n)), each of the following:
   1. If f(n) = O(g(n)) and g(n) = O(h(n)) then f(n) = O(h(n)).

   ANSWER:
   
   From f(n) = O(g(n)) we know that there exist positive constants c and r such that

   f(n) ≤ c * g(n) ∀ n ≥ r

   From g(n) = O(h(n)) we know that there exist positive constants d and s such that

   g(n) ≤ d * h(n) ∀ n ≥ s

   Both inequalities will hold if n ≥ r and n ≥ s. We can therefore conclude that:

   f(n) ≤ c * g(n) ≤ c * (d * h(n)) ∀ n ≥ max(r,s)

   Thus we have shown that there exist positive constants k = c*d and n₀ = max(r,s) such that

   f(n) ≤ k * h(n) ∀ n ≥ n₀

   2. If f₁(n) = O(g₁(n)) and f₂(n) = O(g₂(n)) then f₁(n) f₂(n) = O(g₁(n)g₂(n))

   ANSWER:
   
   From f₁(n) = O(g₁(n)) we know that there exist positive constants c₁ and n₁ such that

   f₁(n) ≤ c₁ * g₁(n) ∀ n ≥ n₁

   From f₂(n) = O(g₂(n)) we know that there exist positive constants c₂ and n₂ such that

   f₂(n) ≤ c₂ * g₂(n) ∀ n ≥ n₂

   Both inequalities will hold if n ≥ n₁ and n ≥ n₂. We can therefore conclude that:

   f₁(n) f₂(n) ≤ c₁ * g₁(n) * c₂ * g₂(n) ∀ n ≥ max(n₁,n₂)

   or

   f₁(n) f₂(n) ≤ c₁ * c₂ * g₁(n) * g₂(n) ∀ n ≥ max(n₁,n₂)