Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
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 4:08
add comment

1 Answer 1

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|improve this answer
    
Ah, it was the base 2 that I forgot. Thank you! –  user52207 Feb 27 '13 at 13:20
add comment

Your Answer

 
discard

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.