Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?

Question

$$\log n+\log \frac{n}{2}+\log\frac{n}{4}+\log\frac{n}{8}+\cdots+\log\frac{n}{n}=\Theta (\log^2n).$$

The sum of logarithms is the logarithm of the product $n\cdot\frac{n}{2}\cdot\frac{n}{4}\cdot\frac{n}{8}\cdots\frac{n}{n}$. This equals $n^{\log n}$ divided by what? If the product would just be $n^{\log n}$, then this would make perfect sende since $ \log(n^{\log n})=\log(n)\cdot\log(n)=\log^2 n$. But the divisor equals $\frac{1}{2}\cdot\frac{1}{4}\cdot\frac{1}{8}\cdot\frac{1}{16}\cdots\frac{1}{n}$ so I don't get it.

Answer 1

Assuming $n$ is a power of $2$, you have: $$ \sum_{i=0}^{\log n} \log \frac{n}{2^i} = \sum_{i=0}^{\log n} \left( \log n - i \right) = \sum_{i=0}^{\log n} i = \frac{(\log n)(\log n+1)}{2} = \Theta(\log^2 n). $$