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²)
2. (5 marks) Prove using only the definition of Big-Oh that 2n² -6n +4 ∈ O(n²)
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))
   
4. (5 marks) Show using the Rules of Big-Oh the following claim.
   
   Claim: 14n²log n + 4n-11² ∈ O(n³).
   
   
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²).
   
   
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).
   
   
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).
   
   
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