寻找谐波系列的大O [英] Finding Big O of the Harmonic Series

问题描述

证明

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

推荐答案

根据微积分中的一个简单事实，很容易做到这一点:

This follows easily from a simple fact in Calculus:

我们有以下不等式:

在这里我们可以得出结论，S = 1 + 1/2 + ... + 1/n都是Ω(log(n))和O(log(n))，因此它是Ɵ(log(n) )，实际上边界是紧密的.

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.

这篇关于寻找谐波系列的大O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！