# $\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?

I am trying to analyze a series that I found, in the analysis of an algorithm. And I was wondering if the following was true: $$\log_{2}{\left(\frac{1}{2}n\right)} + \log_{2}{\left(\frac{1}{4}n\right)} + \log_{2}{\left(\frac{1}{8}n\right)} + \cdots + \log_{2}{\left(\frac{1}{2^{log_{2}(n)}}n\right)} = \mathcal{O}\left(\log_{2}(n)\right)$$

It is basically the sum of the geometric series which converges to $$1$$, but each term is multiplied by $$n$$ and $$\log_{2}$$ is taken.

Using the logarithm rule $$\log_{2}(a) + \log_{2}(b) = \log_{2}(ab)$$ seems to give results that indicate this is not the case right? e.g. $$\log_{2}(128) = 7$$ and $$\log_{2}\left(\frac{1}{2}128\right) + \log_{2}\left(\frac{1}{4}128\right) \ldots = \log_{2}(64) + \log_{2}(32) + \log_{2}(16) + \log_{2}(8) + \log_{2}(4) + \log_{2}(2) = \log_{2}(2097152) = 21$$ So a difference of 14, when $$n=128$$, I suppose that there is no way that this series is upper bounded by like $$\mathcal{O}(10\log_{2}(n))$$.

Using $$\log a + \log b = \log (ab)$$, we get: $$\sum\limits_{k=1}^{\log_2 n}\log_2\left(\frac1{2^k}n\right) = \log_2\left(\prod\limits_{k=1}^{\log_2 n}\frac{n}{2^k} \right) = \log_2\left(\frac{n^{\log_2 n}}{2^{\sum\limits_{k=1}^{\log_2 n}k}}\right) = \log_2\left(\frac{n^{\log_2 n}}{2^{\frac{\log_2 n\times(\log_2 n + 1)}{2}}}\right)$$

But: $$\frac{n^{\log_2 n}}{2^{\frac{\log_2 n\times(\log_2 n + 1)}{2}}} = \frac{n^{\log_2 n}}{n^{\frac{\log_2 n + 1}{2}}} = n^{\frac{\log_2 n - 1}{2}}$$

We conclude that the sum is equal to: $$\log_2 \left(n^{\frac{\log_2 n - 1}{2}}\right) = \frac{\log_2 n - 1}{2}\log_2 n \in \Omega((\log n)^2)$$

Another way to get this result is to say that half (so $$\frac12\log_2 n$$) of the terms of the sum are greater than $$\log_2(\sqrt{n})$$.

Let $$k:=\log_2 n$$ then

$$\sum\limits_{j=1}^{\log_2 n}\log_2(\frac{1}{2^j} \cdot n) = \sum\limits_{j=1}^{k}(\log_2(\frac{2^k}{2^j})) = \sum\limits_{j=1}^{k}\log_2(2^j) = \sum\limits_{j=1}^{k} j = \frac 1 2 k(k+1)$$

so

$$\sum\limits_{j=1}^{\log_2 n}\log_2(\frac{1}{2^j} \cdot n) \in \Theta(k^2) =\Theta((\log_2 n)^2)$$

• Shouldn't it be $\sum\limits_{j=0}^{k-1}j$ instead of $\sum\limits_{j=1}^kj$? That doesn't change the $\Theta$, though. Mar 14 at 12:00

Yet another way to obtain the bound using the identity $$\log \frac ab=\log a - \log b$$ to have simpler sums.

$$\sum\limits_{i=1}^{\log_2 n} \log_2 \left({\frac{n}{2^i}}\right) = \sum\limits_{i=1}^{\log_2 n} \left(\log_2 n - \log_2 2^i \right) = \sum\limits_{i=1}^{\log_2 n} \left(\log_2 n - i \right) = \sum\limits_{i=1}^{\log_2 n} \log_2 n - \sum\limits_{i=1}^{\log_2 n} i$$

We now have,

$$\sum\limits_{i=1}^{\log_2 n} \log_2 n - \sum\limits_{i=1}^{\log_2 n} i = (\log_2 n)^2 - \left(\frac {\left(\log_2n\right)^2}{2} + \frac{\log_2 n}{2}\right) = \frac {\left(\log_2n\right)^2}{2} - \frac{\log_2 n}{2} = \Theta\left( \left(\log_2 n\right)^2 \right)$$