Logarithm, its algebraic properties and algorithmic complexity (MIT OpenCourseware 6.042)

Question

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.

Answer 1

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