Wednesday, November 5, 2014

Secret relationships? L'Hopital's Rule and Big-Oh

It was refreshing to see something familiar during this week's lecture: L'Hospital Rule.  As fascinated as I am with calculus, seeing L'Hopital's Rule used with Big-Oh didn't quite make sense at all... How are they even related?

Suppose there are two functions f and g.  If the ratio f(n) / g(n) approaches infinitely, then the function f(n) grows faster than g(n).  The following graph is a good representation:

But how is this related to Big-Oh, or limits for that matter?

Proving Big-Oh can prove (no pun intended) to be tricky at times and therefore an alternative method is required.

Proving that the ratio mentioned previously approaches infinity means that that f is in Big-Oh of g, as function f grows faster than g!

There is a secret connection between the definition of Big-Oh and that of limits; relating the two definitions in terms of symbols can prove a Big-Oh statements.

This is where L'Hopital's rule comes into play.  Finding the limit of the ratio as it approaches infinity may be more easily done by taking the limit of ration of derivatives of the functions.


There are no restrictions to the number of times you can take the derivatives to reach the result that truly approaches infinity.

No comments:

Post a Comment