Show that $\sum_{i=1}^{n}[\log_{2}(n/i)]$ is O(n), hint use Stirling's Approximation

Question

Assume that n is a power of 2. Hint 1: Use induction to reduce the problem to that for n/2. Hint 2: Alternative hint -> use Stirling's Approximation. Im trying to solve this problem using the lime rule for big oh which says the lim n->inf (f(n)/g(n)) = 0≤c< inf. My instictive approach would be to use arithmetic sequence formula to simplify the summation into something i can take the limit of but im not sure what I would do with i. Does the i become a factorial?

Answer 1

Hint: Recall that $\log(a) + \log(b) = \log(ab)$. Applying this to your case gives $$ \sum\limits_{i = 1}^n \log_2(n/i) = \log_2\left(\prod_{i = 1}^n \frac{n}{i} \right) = \log_2 \left( \frac{n^n}{n!}\right). $$

Can you complete the problem with Stirling's formula?

---

Edit: We have \begin{align*} \log_2 \left( \frac{n^n}{n!}\right) &= \frac{1}{\ln 2}\left(n \ln(n) - \ln(n!) \right) \\ &= \frac{1}{\ln 2}\bigg(n \ln(n) - \Big[n \ln(n) - n + O(\ln(n)) \Big] \bigg) &\text{ by Stirling's formula} \\ &=\frac{1}{\ln 2}\bigg(n - O(\ln(n)) \bigg) \\ &= O(n). \end{align*}