Exercise III
- Use the mathematical definition of Big-Oh to show the asymptotic running time of a given program.
Consider the following function describes the precise running time of an algorithm:
Exercise Show .
Solution
We can choose and for the definition of Big-Oh to hold.
Recall the choice of and are not unique.
There can be many (actually, infinitely many) different combinations of and that would make the Big-Oh definition to work. It depends on what inequalities you use while doing the upper-bounding.
Exercise Show .
Solution
We can choose and for the definition of Big-Oh to hold.
Big-Oh expresses an upper bound but does not necessarily provide a tight upper bound.
For example, you can easily show for any .
Exercise Show .
Solution
There simply is no and where the Big-Oh definition would hold for .