1

If $\displaystyle{f(n)=an^2+bn+c}$ with $\displaystyle{a>0}$ then $\displaystyle{f(n)=\Theta{(n^2)}}$.

Generally, if $\displaystyle{f(n)=\sum_{i=0}^{d}a_in^i}$ with $\displaystyle{a_d>0}$ then $\displaystyle{f(n)=\Theta{(n^d)}}$.

$$$$

But what happens if $\displaystyle{a_d<0}$ ??

Mary Star
  • 13,956

1 Answers1

3

It's also $f(n)=\Theta(n^d)$, multiply inequalities in definion of $\Theta(n^d)$ by $-1$.

agha
  • 10,038
  • Ahaa...Ok!! Thank you very much!!! :-) – Mary Star Jul 09 '14 at 20:44
  • The definition of $\displaystyle{f(n)=\Theta(n^d)}$ is the following: $$\exists c_1, c_2 >0, n_0 \geq 1 \text{ such that } \forall n \geq n_0 : c_1 n^d \leq f(n) \leq c_2 n^d$$ $\displaystyle{c_1}$ could be for example $\displaystyle{\frac{a_d}{2}}$, couldn't it? What could $\displaystyle{c_2}$ be?? – Mary Star Jul 17 '14 at 21:39