Finding Big O of the Harmonic Series

Time ComplexityBig OComplexity Theory

Time Complexity Problem Overview

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

Time Complexity Solutions

Solution 1 - Time Complexity

This follows easily from a simple fact in Calculus:

enter image description here

and we have the following inequality:

enter image description here

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 - Time Complexity

Here's a formulation using Discrete Mathematics:

enter image description here So, H(n) = O(log n)

Solution 3 - Time Complexity

If the problem was changed to :

1 + 1/2 + 1/4 + ... + 1/n

series can now be written as:

1/2^0 + 1/2^1 + 1/2^2 + ... + 1/2^(k)

How many times loop will run? 0 to k = k + 1 times.From both series we can see 2^k = n. Hence k = log (n). So, number of times it ran = log(n) + 1 = O(log n).

Categories
Recommended Time Complexity Solutions
Recommended Big O Solutions
Recommended Complexity Theory Solutions

Previous Solution:

Auto Layout in UICollectionViewCell not working

IosUicollectionviewAutolayoutUicollectionviewcell

Next Solution:

Git - Cherry pick a single commit for pull request

GitGithub

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
Questionuser2092408View Question on Stackoverflow
Solution 1 - Time ComplexitychiwangcView Answer on Stackoverflow
Solution 2 - Time ComplexitySushovan MandalView Answer on Stackoverflow
Solution 3 - Time ComplexitySahim SalemView Answer on Stackoverflow