1. Prove that f (n) =10n4 +2n2 +3is O(n4), provide the appropriate C and k constants.
2. Prove that f (n) = 2n2 −n logn+3lognis O(n2), provide the appropriate C and k constants.
3. Prove that f (n) = 2n4 logn4 −n2 +3logn is O(n4 log n), provide the appropriate C and k constants.
4. Prove or disprove
f (n)=5n3 −n+3
:
a. f(n) = O(n2)
b. f(n) = Ω(n)
c. f(n) = ϴ(n3)
d. f(n) = ω(n)
e. f(n) = o(n2)
Provide the appropriate C and k constants if possible (for parts a,b,c).
5. Prove that (𝑛 + 5)100 = Ѳ(𝑛100).
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:
a. f (n) = n and g(n) = n1+sin n .
b. 𝑓 and 𝑔(𝑛) = n + sin(n)
c. 𝑓(𝑛) = 𝑛 and 𝑔(𝑛) = n ∗ |sin(n)|
9. Prove or disprove: 2n+1=O(2n).
10. Prove or disprove: 22n=o(2n).
f (n)
11. Prove that if lim ⎯⎯→ = C , for some constant C0, 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)
f (n)
| −
