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.