Q:

Prove that $\sum_{i=1}^{i=n} \left\lfloor \frac{n}{i} \right\rfloor = \Theta(n \log n)$

I am trying to prove whether the function $f(k) = \sum_{i=1}^{i=n} \left\lfloor \frac{n}{i} \right\rfloor$ is $\Theta(n \log n)$. 
I can show that $n \log n - n \leq f(n) \leq n \log n$ which means that there is a constant $c_2 = 1$ for which $f(n) \leq c_2 n \log n$ but I am stuck on the lower bound i.e finding a constant $c_1$ such that $c_1 n \log n \leq f(n)$. Any help is appreciated!

A:

For sufficiently large $n$, we have
$$ \frac{n\log n}{2} \leq n\log n - n $$
Alternatively, just divide all three sides of your inequality by $n\log n$ to conclude that $f(n)/(n\log n)$ is bounded.

