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.
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}$$