Exercise III

  • Use the mathematical definition of Big-Oh to show 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 \Omicron(n^2)$.

Solution

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

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

Recall the choice of $n_0$ and $c$ are not unique.

There can be many (actually, infinitely many) different combinations of $n_0$ and $c$ that would make the Big-Oh definition to work. It depends on what inequalities you use while doing the upper-bounding.

Exercise Show $T(n) \in \Omicron(n^3)$.

Solution

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

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

Big-Oh expresses an upper bound but does not necessarily provide a tight upper bound.

For example, you can easily show $T(n) \in \Omicron(n^p)$ for any $p \ge 2$.

Exercise Show $T(n) \notin \Omicron(n)$.

Solution

There simply is no $c$ and $n_0$ where the Big-Oh definition would hold for $T(n) \in \Omicron(n)$.