Week 9

This week, we had some examples of proving a function is in O(another function).
For example, to prove a function is not in O(n square), we need to prove:

And to prove a function is not in O(n square), we need to prove the negation of the above expression.

This is the way to prove polynomial functions.

Then, we know logarithmic functions are in big-Oh of any polynomial, whereas exponential functions (with a base bigger than 1) are not in big-Oh of any polynomial.
So, to prove exponential function is not in big-Oh of n square: