This week we worked on more proofs involving big-Oh, big-Omega, and saw a glimpse of big-Theta, which probably aims to prove that a function has the same growth rate as another function, since it involves both the lower and upper bound with two different coefficients.
I had the most difficulty trying to understand Monday's lecture about incorporating L'Hôpital's rule into a proof. When we are asked to prove that 2^n is not in big-Oh of n^2, it is easy to think that an exponential function with base greater than 1 probably outgrows any sort of polynomial at some point, but it's hard to intuitively view it as a limit of a ratio (2^n) / (n^2) as n approaches infinity. Using L'Hôpital's rule we were able to evaluate the limit to be positive infinity, which suggests that there is no positive real number C such that when multiplied with n^2 will produce a value that is definitely larger than 2^n on the domain of this ratio. But the result of the limit made me wonder, what if n^2 were changed to -(n^2)? Then the limit would evaluate to negative infinity. Graphically, there is no doubt that 2^n is not upper-bounded to -(n^2), since one lies above and one lies below the x-axis. So then, does the negative infinity mean we have to find some number C that is less than negative infinity (although certainly there isn't any)? What if some other limit of ratio evaluates to a negative finite number, does that mean we automatically get the disproof, given that C must be a positive real number? What if the ratio were inverted, so limit as n approaches infinity of (n^2) / (2^n) evaluates to zero, how should we start looking for C and B?
No comments:
Post a Comment