Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 4:08
up vote 3 down vote accepted

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

share|cite|improve this answer
Ah, it was the base 2 that I forgot. Thank you! – user52207 Feb 27 '13 at 13:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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