Again, since I'm pursuing Computer Science degree as my second degree, any course I've already taken that overlap U of T courses is in the list of exclusion. That means, I supposed to know the material.
Well... maybe I'm lucky or not, only Calculus I have to remember is L'Hopital's Rule. (And derivatives, of course).
Basically, when limit of n tends to sigma where 2^n / n^2 = sigma. It's obvious that 2^n is much larger than n^2. But this is still not quite intuitive. So we take derivatives of both numerator and denominator until we find a constant.
d(2^n) / d(n^2) = ln2*2^n / 2n
d(ln2*2^n) / d(2n) = ln2*ln2*2^n / 2
Voila! Now we can intuitively see that this function gets enoumously large when n tends to sigma (infinity).
Here is my course note for proving n^2 is not element of Big-Oh(2^n).
Click the image to enlarge.
No comments:
Post a Comment