Week 9

    In this week, calculus has once again sneaked its way into CSC165. In particular, limits, and L'hopital's rule are being applied in order to solve big O proofs. As an example of how this can be applied to big O, the lecture slides show that n^2 is not in the big O of 2^n. Intuitively, this makes sense. No matter what positive multiple of 2^n is picked, it will eventually grow larger than n^2. This makes even more sense when shown with limits.  L'hopital's rule states that:

as long as some other conditions are met (which are true for 2^n / n^2). Taking the second derivative of the limit of 2^n / n^2 as n goes to infinity shows that 2^n / n^2 goes to infinity. The reason this is helpful is because it shows that 2^n will always be larger than n^2 at some point as n gets really big. However, this is still not proof that n^2 is not in big O of 2^n but it provides the necessary tools for that proof. And it's really neat.