Unlike a decreasing geometric series, the sum of the harmonic series 1, 1/2, 1/3, 1/4, 1/5, . . di- log(n! ) = θ(n log n). verges; that is, it turns out that, for large n, the sum of the first n terms of this series can be well approximated as 1 ≈ ln n + γ, i=1 i where ln is natural logarithm (log base e = 2.718 . .) and γ is a particular constant 0.57721 . .. showthat 1 = θ(logn). i=1 i (hint: to show an upper bound, decrease each denominator to the next power of two. for a lower bound, increase each denominator to the next power of 2.)