Handy Maths to solve Data Structure Problem

Let me first define the problem:

Prob: F(n) is a function defined as :

F(n) = 1 ; n = 1

F(n) = F(n-1) + 1/n ; n>1

Prove that Big Oh of F(n) is log n

Solution:

F(n) = F(n-1) + 1/n

= F(n-2) + 1/(n-1) + 1/n

=F(n-3) + 1/(n-2) + 1/(n-1) + 1/n

This kind of series is called the Harmonic Series and can be represented as 1 + 1/2 + 1/3 + 1/4 + ......+ 1/n

Mathematically we can prove that the sum of an Harmonic series is ln n + gamma( a constant). This constant is called Euler's constant and its approx value is 0.57721

Therefore, we can say limit   f(n) = limit ln n + gamma

                               n->infinity       n->infinity

Hence                limit   f(n)/log n 

                         n->infinity 

                       = limit (ln n + gamma)/log n

                          n->infinity

                       = limit ln n/log n  +  gamma/limit log n

                           n->infinity                  n->infinity

                       = ln 2 + 0

                       = ln 2

Hence we can say F(n) = O(log n)

You can find the document here.