Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

About Logarithms

In this section we determine the asymptotic behavior of logarithms. Interestingly, despite the fact that tex2html_wrap_inline58789 diverges as n gets large, tex2html_wrap_inline58793 for all integers tex2html_wrap_inline58277. Hence, tex2html_wrap_inline58797. Furthermore, as the following theorem will show, tex2html_wrap_inline58789 raised to any integer power tex2html_wrap_inline58801 is still O(n).

Theorem  For every integer tex2html_wrap_inline58801, tex2html_wrap_inline58807.

extbfProof This result follows immediately from Theorem gif and the observation that for all integers tex2html_wrap_inline58801,


This observation can be proved by induction as follows:

Base Case Consider the limit


for the case k=1. Using L'Hôpital's rulegif  we see that


Inductive Hypothesis Assume that Equation gif holds for tex2html_wrap_inline58831. Consider the case k=m+1. Using L'Hôpital's rule  we see that


Therefore, by induction on m, Equation gif holds for all integers tex2html_wrap_inline58801.

For example, using this property of logarithms together with the rule for determining the asymptotic behavior of the product of two functions (Theorem gif), we can determine that since tex2html_wrap_inline58797, then tex2html_wrap_inline58841.

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.