Exercise V

Use the mathematical definition of Big Omega to prove the asymptotic running time of a given program.

Consider the following function $T(n)$ describes the precise running time of an algorithm:

$T(n) = 3n^2 - 100n + 6$

Exercise Show $T(n) \in \Omega(n^2)$ .

Solution

We can choose $c=2$ and $n_0=100$ for the definition of Big-Oh to hold.

$2n^2 < 3n^2 - 100n + 6$

Similar to the definition of Big-Oh, the choice of $n_0$ and $c$ are not unique.

Exercise Show $T(n) \in \Omega(n)$ .

Solution

For any $c$ and $n_0=100c$ , the definition of Big-Oh to hold.

$cn \le 3n^2 - 100n + 6$

Big-Omega expresses a lower bound, but it is not necessarily a tight lower bound.

Exercise Show $T(n) \notin \Omega(n^3)$ .

Solution

We can choose $c=1$ and for any $n > 1$ we have

$3n^2 - 100n + 6 \le n^3$

So $n^3$ is really an upper bound for $T(n)$ and not a lower bound.

CS226 Homepage