# 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)$?

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

• Try to write the summation in the form $\sum_{i=0}^{\log n} a_i$ for a suitable $a_i$ (which also depends on $n$). Then you will likely find a better way to deal with the logarithm. – Discrete lizard Jul 31 '20 at 12:17

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).$$
• Thanks a lot! Why is $\sum_{i=0}^{\log n} \left( \log n - i \right) = \sum_{i=0}^{\log n}i$? – timtam Jul 31 '20 at 13:02
• The addends of the first sums are the integers from $\log n$ to $0$, in descending order. The addends of the second sum are the same integers but in ascending order. – Steven Jul 31 '20 at 13:03