Assignment value: 0%

Assignment submission: Problems should be completed by Thursday class. Do not hand them in; we will take them up in class.

Questions:

1. (5 marks) Prove using only the definition of Big-Oh (and appropriate use of "≤") that 3n log n - 60 ∈ O(n²)
   Solution:
   

   3n log n - 60	≤ 3n log n for all n
   	≤ 3n2 for all n ≥ 1

   
   Therefore the claim is witnessed by c = 3 and n₀ = 1.
   
2. (5 marks) Prove using only the definition of Big-Oh that 2n² -6n +4 ∈ O(n²)
   Solution:
   

   2n 2 - 6n + 4	≤ 2n2 +4 for all n
   	≤ 3n2 for all n ≥ 2 (since when n ≥ 2, n2 ≥ 4 -- but you don't have to state this parenthetical comment in your answer)

   
   Therefore the claim is witnessed by c = 3 and n₀ = 2. ☐
   
3. (5 marks) Prove the Transitivity of Big Oh Rule. You can use the definition of big-O and any other big-O Rules in your proof.
   
   Transitivity of Big-Oh Rule: If f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)) then f(n) ∈ O(h(n))
   Solution:
   Suppose f(n) ∈ O(g(n)) and g(n) ∈ O(h(n)).
   Then there exist positive constants c₁, n₁, c₂, n₂, such that
   f(n) ≤ c₁ g(n) for all n ≥ n₁, and
   g(n) ≤ c₂ h(n) for all n ≥ n₂.
   Substituting c₂ h(n) for g(n) in the first equation, we obtain that
   f(n) ≤ c₁ c₂ h(n) for all n ≥ max(n₁ n₂).
   Therefore the claim is witnessed by c = c₁*c₂ and n₀ = max(n₁ n₂). ☐
   
   
   
4. (5 marks) Show using the Rules of Big-Oh the following claim.
   
   Claim: 14n²log n + 4n-11² ∈ O(n³).
   
   Solution:

   1. log n ∈ O(n)	Log Dom
   2. 14 n2 ∈ O(n2)	CF (or Polynomial)
   3. 14 n log n ∈ O(n3)	1,2 Product
   4. 4 n -112 ∈ O(n3)	Polynomial
   5. 14 n log n + 4n - 112∈ O(n3)	3,4 Sum ☐

   
   
   
5. (5 marks) Show using the Rules of Big-Oh, and/or using the definitions of Big-Oh and Θ, the following claim.
   
   Claim: 6n² + 2n +1 ∈ O(n²).
   
   Solution:

   1. 6n2 +2n +1 ∈ O(n2)

   Polynomial

6. (5 marks) Show using the Rules of Big-Oh, and/or using the definitions of Big-Oh and Θ, the following claim.
   
   Claim: 0.1 n⁴log n + 2n +1 ∈ Θ(n⁴log n).
   
   Solution: In one direction:

   1. 0.1 n4log n ∈ O(n4log n)	Constant Factors
   2. 2 n+ 1∈ O(n4)	Polynomial
   3. 1 ∈ O(log n)	Less Than
   4. 2 n+ 1∈ O(n4log n)	2,3 Product Rule
   5. 0.1 n4log n + 2 n+ 1∈ O(n4log n)	1,4 Sum Rule

   
   In the other direction:

   n4log n	≤ n4log n + 20n +10 ∀ n ≥ 1
   	≤ 10( 0.1n4 2n + 1) ∀ n ≥ 1

   
   Therefore by the definition of Big Oh, n⁴log n ∈ O(0.1 n⁴log n + 2n +1) ☐


7. (5 marks) Show using the definition of Big-Oh the following claim:
   
   Claim: n² log n is not in O(n²log log n).
   
   Solution:
   Proof: The proof is BWOC (by way of contradiction).
   Suppose n² log n ∈ O(n²log log n).
   Then from the definition of Big-Oh, there exist positive constants c and n₀ such that
   n² log n ≤ c n²log log n ∀ n ≥ n₀
   Therefore log n ≤ c log log n ∀ n ≥ n₀
   Therefore 2^{log n} ≤ 2^{c log log n} ∀ n ≥ n₀
   Therefore n ≤ log ^cn ∀ n ≥ n₀
   But this violates a known fact that any positive power of n grows faster than any positive power of log n. ☐
   
8. Order the following functions in order of increasing growth rate: i.e., list the slowest growing functions (in the Big-Oh sense) first and the fastest growing last.
   3n log n + 100
   n²/(log n)
   2ⁿ
   2²ⁿ
   2ⁿ⁺¹
   0.3412 n²
   4 n² + 5 √n + 19
   4 n² -16n
   6 n^3.1
   n^3.01
   
   Solution:
   3n log n + 100, n²/(log n), {0.3412 n², 4 n² + 5 √n + 19, 4 n² -16n}, n^3.01, 6 n^3.1, {2ⁿ, 2ⁿ⁺¹}, 2²ⁿ