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