PHD Discussions Logo

Ask, Learn and Accelerate in your PhD Research

Question Icon Post Your Answer

Question Icon

Can harmonic numbers Hn = 1 + 1/2 + ... + 1/n be calculated using a constant number of operations?

In my algorithm design work, I need to know if computing H_n exactly is inherently an O(n) task or if there exists a clever closed-form formula or algorithm that achieves O(1) time complexity. This distinguishes between a fundamental cost and an engineering optimization.

All Answers (1 Answers In All)

By Pragya Chauhan Answered 1 year ago

In the standard model of computation using basic arithmetic (+, ÷), I can definitively say no, you cannot compute the exact rational value of H_n in a constant number of operations. There is no known closed-form formula that bypasses the need to sum the n terms. Each term 1/k requires an operation, so the complexity is inherently Ω(n). However, for practical purposes with floating-point approximations, you can use asymptotic formulas like the Euler-Mascheroni expansion (H_n ≈ ln n + γ) for large n, which is O(1), but that's an approximation, not exact computation.

 

Your Answer