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)T(n) describes the precise running time of an algorithm:

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


Exercise Show T(n)O(n2)T(n) \in \Omicron(n^2).

Solution

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

3n2100n+63n2 3n^2 - 100n + 6 \le 3n^2

Recall the choice of n0n_0 and cc are not unique.

There can be many (actually, infinitely many) different combinations of n0n_0 and cc 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)O(n3)T(n) \in \Omicron(n^3).

Solution

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

3n2100n+6n3 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)O(np)T(n) \in \Omicron(n^p) for any p2p \ge 2.

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

Solution

There simply is no cc and n0n_0 where the Big-Oh definition would hold for T(n)O(n)T(n) \in \Omicron(n).