0

I want to prove that big theta notation of the harmonic series is $\Theta(\log n)$. I want to work with integral to show that.

I attempted this:

$$\ln(n)=\int^n_1 \frac{dx}x \le \sum _{k=1} ^n \frac1k \le 1 + \int^n_2 \frac{dx}x = 1 + \ln(n)$$ This approach was not demanded, because I have not proven that $\Theta(\log n)$ is a tight bound for the harmonic series.

How can I show this, and how to overcome this obstacle? Please help.

Thanks.

Thumbnail
  • 563
user11001
  • 123

1 Answers1

-1

If we extend the definition of $=$ and $\le$ to $\Theta$s in the obvious way, you have shown that

$$\begin{align} \Theta \ln (n) &= \Theta \int^n_1 \frac{dx}x \\ &\le \Theta \sum _{k=1} ^n \frac1k \\ &\le \Theta (1 + \int^n_2 \frac{dx}x) \\ &= \Theta (1 + \ln(n)) \\ \text {which, since } \Theta (1) \lt \Theta (\ln (n))\text {, }\\ &= \Theta \ln (n) \\ \end{align}$$

Thumbnail
  • 563