Let me first define the problem:

Solution:

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

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

You can find the document here.

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

You can find the document here.

## 1 comment:

Thanks for the extra info sir.

Post a Comment