Consider the function f(n) = n
2 + 1000n, and do the following:
a) Prove that f(n) = O(n
3
) by finding a c0 and n0 such that f(n) ≤ c0 · n
3
for n > n0.
b) Prove that f(n) = O(n
2
) by finding a c1 and n1 such that f(n) ≤ c1 · n
2
for n > n1.
c) Prove that f(n) = Ω(n
2
) by finding a c2 and n2 such that f(n) ≥ c2 · n
2
for n > n2.
d) Prove that f(n) = Θ(n
2
) by finding a c3, c
′
3
, and n3 such that c3 · n
2 ≤ f(n) ≤ c
′
3
· n
2
for n > n3
