3

Does $$2^{\log{n}} T(n / 2^{\log n}) = 2^{\log{n}} T(1)?$$ If so, how?

Also, I don't understand how the following equality works:

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

I'm afraid I'm either missing some context or just algebraic properties. It seems like the latter equality is a property that I'm supposed to know or be given? Prof. Leighton performs this calculation in the first lecture (approx. 32:17) of the Mathematics for Computer Science course for OCW, when analyzing the Merge-Sort algorithm.

Gerry Myerson
  • 179,216
user52207
  • 95
  • 3
  • 2
    The second equality is just a special case of:

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

    which can be proved using induction. It can also be viewed as the first $n+1$ terms of a geometric series:

    $$ \sum_{i=0}^n x^i = \frac{x^{n+1} - 1}{x -1} \qquad (\text{ for } x \neq 1) $$

     – JavaMan Feb 27 '13 at 04:08

1 Answers1

3

Keep in mind that log in CS almost always means log base 2. So in particular, $2^{\log n}=n$ (from the definition of log, obviously), which is how $n/{2^{\log n}}$ becomes 1.

There's all sorts of ways to interpret the second formula. One way is to think of it in terms of binary representation. Note that $\sum_{i=0}^N{2^i}$ is the same as the N-digit binary number that consists of all 1s. E.g. for $N=4$: $1111_2$. Add one to this number and you get $10000_2$, which represents $2^5=2^{N+1}$. Subtract the one to get $2^{N+1}-1$.

amr
  • 495