|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
In this section we determine the asymptotic behavior of logarithms.
Interestingly,
despite the fact that 
diverges as n gets large,
for all integers 
. Hence, 
.
Furthermore, as the following theorem will show,
raised to any integer power 
is still O(n).
Theorem For every integer.
extbfProof
This result follows immediately from Theorem 
and the observation that for all integers ,
This observation can be proved by induction as follows:
Base Case Consider the limit
for the case k=1.
Using L'Hôpital's rule
we see that
Inductive Hypothesis
Assume that Equation holds for 
.
Consider the case k=m+1.
Using L'Hôpital's rule we see that
Therefore, by induction on m, Equation
holds for all integers .
For example,
using this property of logarithms
together with the rule for determining the asymptotic behavior
of the product of two functions (Theorem ),
we can determine that since ,
then 
.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.
