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.