**Next:**1.3
To Probe Further**Up:**1.2
Complexity of Algorithms**Previous:**1.2.6
Big Omega and Big Theta Notations

##
1.2.7 An Example:

Let *f*
(*n*) = 2*n*^{2} + 4*n* + 10. *f*
(*n*) is O(n^{2}). For,
*f* (*n*)
3*n*^{2}
*n*
6

Thus, C = 3 and *n*_{0} = 6

Also,

*f* (*n*)
4*n*^{2}
*n*
4

Thus, *C* = 4 and *n*_{0}
= 4

*f* (*n*) is O(n^{3})

In fact, if *f* (*n*) is
*O*(*n*^{k}) for some *k*,
it is *O*(*n*^{h}) for *h*
> *k*

*f* (*n*) is not *O*(*n*).

Suppose
a constant C such that

2*n*^{2} + 4*n* + 10 *Cnnn*_{0}

This can be easily seen to lead to a contradiction. Thus,
we have that:

*f* (*n*) is (*n*^{2})
and *f* (*n*) is (*n*^{2})

eEL,CSA_Dept,IISc,Bangalore