2
$\begingroup$

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

$\endgroup$

3 Answers 3

5
$\begingroup$

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

So the answer is no.

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Mar 14 at 12:00
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.