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

About Harmonic Numbers

 

The series tex2html_wrap_inline57693 is called the harmonic series , and the summation

displaymath57689

gives rise to the series of harmonic numbers , tex2html_wrap_inline57695, tex2html_wrap_inline57697, .... As it turns out, harmonic numbers often creep into the analysis of algorithms. Therefore, we should understand a little bit about how they behave.

A remarkable characteristic of harmonic numbers is that, even though as n gets large and the difference between consecutive harmonic numbers gets arbitrarily small ( tex2html_wrap_inline57701), the series does not converge! That is, tex2html_wrap_inline57703 does not exist. In other words, the summation tex2html_wrap_inline57705 goes off to infinity, but just barely.

Figure gif helps us to understand the behavior of harmonic numbers. The smooth curve in this figure is the function y=1/x. The descending staircase represents the function tex2html_wrap_inline57709.gif

   figure644
Figure: Computing harmonic numbers.

Notice that the area under the staircase between 1 and n for any integer n>1 is given by

eqnarray747

Thus, if we can determine the area under the descending staircase in Figure gif, we can determine the values of the harmonic numbers.

As an approximation, consider the area under the smooth curve y=1/x:

eqnarray759

Thus, tex2html_wrap_inline57761 is approximately tex2html_wrap_inline57763 for n>1.

If we approximate tex2html_wrap_inline57761 by tex2html_wrap_inline57763, the error in this approximation is equal to the area between the two curves. In fact, the area between these two curves is such an important quantity that it has its own symbol, tex2html_wrap_inline57771 , which is called Euler's constant . The following derivation indicates a way in which to compute Euler's constant:

eqnarray772

A program to compute Euler's constant on the basis of this derivation is given in Program gif. While this is not necessarily the most accurate or most speedy way to compute Euler's constant, it does give the correct result to six significant digits.

   program801
Program: Program to compute tex2html_wrap_inline57771.

So, with Euler's constant in hand, we can write down an expression for the tex2html_wrap_inline57777 harmonic number:

  equation810

where tex2html_wrap_inline57779 is the error introduced by the fact that tex2html_wrap_inline57771 is defined as the difference between the curves on the interval tex2html_wrap_inline57783, but we only need the difference on the interval [1,n]. As it turns out, it can be shown (but not here), that there exists a constant K such that for large enough values of n, tex2html_wrap_inline57791.gif

Since the error term is less than 1/n, we can add 1/n to both sides of Equation gif and still have an error which goes to zero as n gets large. Thus, the usual approximation for the harmonic number is

displaymath57690

We now return to the question of finding the average running time of Program gif, which finds the largest element of an array. We can now rewrite Equation gif to give

eqnarray820


next up previous contents index

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