In the lecture after the second term test, we looked at
proofs of big-O. Proving the big-O of a function based on the formal
mathematical definition of big-O firstly requires picking a c value higher than
the constant factor of the highest order term and picking a B value. For basic
straightforward functions, nothing too
complex needs to be done to finish up the proof. On the other hand, for proving
the big-O of functions based on more complicated functions than just basic
polynomials, we need to go through the processes of upper bounding one function
and lower bounding the original function and then choosing an appropriate c
value to relate the two functions. All of this in order to get a safe estimate
for what the big-O of the original function would be.
Like proofs we have done before, you can also prove the
big-O of a function by negation. The same logic of bounding the B and c values
apply in all big-O proofs. For polynomials figuring out the big-O of a function
in pretty easy as it depends just on the highest degree term of the function.
For non polynomial functions, to prove the big-O of the function, the limit needs
to be taken. One needs to connect the definition of a limit to that of big-O.
This is done in three steps:
1. Use L'Hopital's rule to show that the limit of the ratio
of a function by a function that is its big-O goes to infinity as the variable(n)
of the function goes to infinity.
2. The limit
determined in step one is converted to the formal definition of a limit.
3. That is then related to the formal definition of big-O.
3. That is then related to the formal definition of big-O.
