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