2
$\begingroup$

Is there any efficient way to solve $F(n)=F(n-1)+1/n$ on $\mathcal{O}(\log n)$ time like we have matrix expo. for fibonacci series ?

$\endgroup$
1

1 Answer 1

0
$\begingroup$

Another way of writing $F(n)$ is:

$F(n) = F(0) + \displaystyle \sum_{k=1}^{n} \frac{1}{k} = F(0) + H_{n}$

where $H_n$ is the $n$th harmonic number.

The exact value of a harmonic number can't be calculated in $\mathcal{O}(\log{n})$, but you can compute an approximation. Assuming this is a programming problem, that should be enough.

Referencing Wikipedia:

http://en.wikipedia.org/wiki/Harmonic_number

$H_n \sim \ln{n} + \gamma + \frac{1}{2n} - \displaystyle \sum_{k=1}^\infty \frac{B_{2k}}{2kn^{2k}} = \ln{n} + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{1}{120n^4} - \cdots$

Where $\gamma$ is the Euler-Mascheroni Constant and $B_k$ are the Bernoulli numbers.

This series should give the desired precision within a few terms.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .