Week 9-Prove big-Oh of non-polynomials using limits

        In this week's class, I was taught how to prove that a non-polynomial function(such as an exponential function) grows faster than a polynomial function. To devise such a proof, I need to first learn the the definition of limits and the L'Hopital Rule. A good thing about this lesson is that I was recently taught the application of the L'Hopital Rule, however, the definition of limit used in CSC165 differs from the one I learned in MAT137. To begin, L'Hopital Rule is used to compute the derivative (or the limit) of a function in the form of f/g, where f and g are functions with g not equal to 0. An example is:

where I applied the L'Hopital Rule twice to obtain a denominator that is not equal to 0.

The value I received is positive infinity, meaning that as n approaches positive infinity 3^n/3n^2 also becomes increasingly large (also positive infinity). In other words, as n increases, 3^n becomes much more larger than 3n^2. This understanding is used to prove that 3^n grows at least as fast as 3n^2.

Now here is a complete example for proof using definition of limits:

        In conclusion, to prove that an exponential function is lower-bounded by a polynomial function, first assume c and B. Then prove that the limit of the exponential function divide by the polynomial function approaches infinity when n also approaches infinity. Later, state the formal definition of the limit and pick n in terms of n' and B. Then, just use the definition of limit to prove the consequent of the definition of lower_bound. To sum up, this type of proof is no different than the materials covered last week (such as the proof for lower- and upper-bound). The only difference is that the definition of limits is applied. Hence, I found this week's class to be very easy to understand.