### Problem

Consider the following recurrence, defined over positive powers of two:

$$T(n)=\[ \begin{cases} 
      c & x = 1 \\
      \lg(n)+2T(\frac{n}{2}) & otherwise
   \end{cases}
\]$$

($$c$$ is a constant; $$\lg$$ is $$\log_2$$)

Compute a closed form for the recurrence via the recursion tree method.

### Scratchwork

$$\log(b/c)=\log(b)-\log(c)$$. $$\log_a(b^c)=c\log_a(b)$$. $$\log_a(a)=1$$. $$a^{\log_a(b)}=b$$

1+2+4+8=15=16-1

$$\sum_{k=0}^{m}[2^k]=2^{k+1}-1$$

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

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

### Sanity checks

Using original definition for $$T(n)$$:

$$
T(1)=c \\
T(2)=\lg(2)+2T(\frac{2}{2}) = 1+2c \\
T(4)=\lg(4)+2T(\frac{4}{2}) = 2+2(1+2c)=4+4c \\
T(64)=???
$$

Using our closed form $$(T(n)=2n-\lg(n)-2+nc)$$:

$$
T(1)=2\cdot 1-\lg(1)-2+1c=2-0-2+c=c\\
T(2)=2\cdot 2-\lg(2)-2+2c=4-1-2+2c=1+2c\\
T(4)=2\cdot 4-\lg(4)-2+4c=8-2-2+4c=4+4c\\
T(64)=2\cdot 64-\lg(64)-2+64c=128-6-2+64c=120+64c\\
$$

### Solution

Internal work: $$\sum_{k=0}^{\lg(n)-1}2^k\lg(\frac{n}{2^k})$$

Leaf work: $$nc$$

$$
T(n)=\sum_{k=0}^{\lg(n)-1}[2^k\lg(\frac{n}{2^k})]+nc \\
=\sum_{k=0}^{\lg(n)-1}[2^k(\lg(n)-\lg(2^k))]+nc \\
=\sum_{k=0}^{\lg(n)-1}[2^k(\lg(n)-k)]+nc \\
=\sum_{k=0}^{\lg(n)-1}[2^k\lg(n)-k2^k]+nc \\
=\sum_{k=0}^{\lg(n)-1}[2^k\lg(n)]-\sum_{k=0}^{\lg(n)-1}[k2^k]+nc \\
=\lg(n)\sum_{k=0}^{\lg(n)-1}[2^k]-\sum_{k=0}^{\lg(n)-1}[k2^k]+nc \\
=\lg(n)(2^{\lg(n)-1+1}-1)-(2+((\lg(n)-1)-1)2^{\lg(n)-1+1})+nc \\
=\lg(n)(n-1)-(2+(\lg(n)-2)n)+nc \\
=n\lg(n)-\lg(n)-(2+n\lg(n)-2n)+nc \\
=n\lg(n)-\lg(n)-2-n\lg(n)+2n+nc \\
=2n-\lg(n)-2+nc \\
$$