Cormen Edition 3 Exercise 2.2 Question 1 (Page No. 29)

Question

Express the function $n^3/1000 -100n^2-100n+3$ in terms of $\Theta$ notation.

Answer 1

I  don't if I am right or wrong ...

if we take very large values of n  then the most governing term in the numerator is n^3 and the most governing term in the denominator is n^2 ...so the overall effect of the function will be decided by n^3 and n^2 ..so function will nearly accomplish the same value as n^3/n^2 ..which might end up giving the value fairly equal to n...so in my view average bound will be best given by the  function

theta(n)

Answer 2

n$^{3}$/1000 − 100n$^{2}$ − 100n + 3  = $\Theta$(n$^{3}$)

For c1=1/2000, c2=1, f(n)=n$^{3}$/1000 − 100n$^{2}$ − 100n + 3  and g(n)= n$^{3}$)

c1*g(n) $\leq$ f(n) $\leq$ c2*g(n) for large values of n