0
$\begingroup$

Skiena's Algorithm Design Manual, 3rd Ed p.71 gives the time complexity of a dynamic array according to the number of movements, $M$, as:

$$ M = n + \sum_{i=1}^{lg(n)} 2^{i-1} = 1 +2+ 4+\ldots+\frac{n}{2} + n \stackrel{?}{=} \sum_{i=0}^{lg(n)} \frac{n}{2^i} $$

For the life of me, I can't figure out how he's getting from the left hand summation to the right hand one. It's crucial that it does, because his next step is to say the right hand side is less than the geometric series as $i\rightarrow\infty$ which converges to $2n$.

There is a known errata,

(*) Page 71, formula on line 10: the lower index of the second summation $i=i$ should be $i=0$.

I have written the right hand side with the correction.

The only possible operations I see are rewriting the exponent...

$$ \sum_{i=1}^{lg(n)} 2^{i-1} = \sum_{i=1}^{lg(n)} 2^i\cdot2^{-1}= \sum_{i=1}^{lg(n)} \frac{2^i}{2} = \frac{1}{2} \sum_{i=1}^{lg(n)} 2^i $$

or adjusting the index...

$$ \sum_{i=1}^{lg(n)} 2^{i-1} = \sum_{i=0}^{lg(n)-1} 2^{i} $$

Neither of which help.

When I expand the right hand side, I get

$$ \frac{n}{1} + \frac{n}{2} + \frac{n}{4} + \frac{n}{8} + \ldots $$

I don't see any way to rearrange or finagle that so it equals $1 +2+ 4+\ldots+\frac{n}{2} + n$.

$\endgroup$
1
  • $\begingroup$ Your expansion $\frac n 1 + \frac n 2 + \frac n 4 + ... $ is the same as the series $1 + 2 + 4 + ... + \frac n 2 + n$, but written in reverse. You might want to figure out the hidden terms in the $...$. $\endgroup$
    – Russel
    Jul 8, 2022 at 2:39

2 Answers 2

1
$\begingroup$

If we assume that $n$ is a power of two (I'm assuming the author assumes this), first we can rewrite $n$ as a power of two, and shift the index over by one. Then we can combine the two into one sum:

$$n + \sum_{i=1}^{\lg(n)} 2^{i-1} = 2^{\lg(n)} + \sum_{i=0}^{\lg(n)-1} 2^{i} = \sum_{i=0}^{\lg(n)} 2^{i}$$

For step two, take a look at this sum reversal identity:

$$\sum_{i=0}^k f(i) = \sum_{i=0}^{k} f(k - i)$$

So we can reverse our sum by substituting $i$ with $\lg(n) - i$:

$$\sum_{i=0}^{\lg(n)} 2^{i} = \sum_{i=0}^{\lg(n)} 2^{\lg (n) - i} = \sum_{i=0}^{\lg(n)} \frac{2^{\lg(n)}}{2^i} = \sum_{i=0}^{\lg(n)} \frac{n}{2^i}$$

$\endgroup$
1
$\begingroup$

$$n+\frac n2+\frac n4\cdots \frac nn=n\left(1+\frac12+\frac14+\cdots\right)\sim n\,2.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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