Finding Big O of the Harmonic Series
51,847
Solution 1
This follows easily from a simple fact in Calculus:
and we have the following inequality:
Here we can conclude that S = 1 + 1/2 + ... + 1/n is both Ω(log(n)) and O(log(n)), thus it is Ɵ(log(n)), the bound is actually tight.
Solution 2
Here's a formulation using Discrete Mathematics:
Author by
Admin
Updated on April 20, 2020Comments
-
Admin about 4 years
Prove that
1 + 1/2 + 1/3 + ... + 1/n is O(log n). Assume n = 2^k
I put the series into the summation, but I have no idea how to tackle this problem. Any help is appreciated