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 ?
1 Answer
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.