[SOLVED] CECS328-Homework 2

Description

1. Prove that f (n) =10n⁴ +2n² +3is O(n⁴), provide the appropriate C and k constants.
2. Prove that f (n) = 2n² −n logn+3lognis O(n²), provide the appropriate C and k constants.
3. Prove that f (n) = 2n⁴ logn⁴ −n² +3logn is O(n⁴ log n), provide the appropriate C and k constants.
4. Prove or disprove
   • (n)=5n³ −n+3

:

1. f(n) = O(n²)
2. f(n) = Ω(n)
3. f(n) = ϴ(n³)
4. f(n) = ω(n)
5. f(n) = o(n²)

Provide the appropriate C and k constants if possible (for parts a,b,c).

5. Prove that (𝑛 + 5)¹⁰⁰ = Ѳ(𝑛¹⁰⁰).
6. Prove transitivity of big-O: if f(n) = O(g(n)), and g(n) = O(h(n)), then f(n) = O(h(n)).
7. Prove that f(n)=O(g(n)) iff g(n)= Ω(f(n)).
8. Compare the growth of:
   1. f (n) = n and g(n) = n^{1+sin n} .
   2. 𝑓 and 𝑔(𝑛) = n + sin(n)
   3. 𝑓(𝑛) = 𝑛 and 𝑔(𝑛) = n ∗ |sin(n)|
9. Prove or disprove: 2ⁿ⁺¹=O(2ⁿ).
10. Prove or disprove: 2²ⁿ=o(2ⁿ).

f (n)

11. Prove that if lim _⎯⎯→ = C , for some constant C>0, then f(n)= ϴ(g(n)). g(n)

f (n)

Hint:  lim _⎯⎯→    = C means that for every ϵ>0, there exists k>=0 such that, for all n>=k,  g(n)

• (n)

|  −C | g(n)