Wednesday, August 25, 2010

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.

1 comment:

Anirban said...

Thanks for the extra info sir.

Share