### Demo 2

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 unrolling method.

### Correctness proof by induction

Claim: $$T(n)=2n-\lg(n)-2+nc$$

Proof by induction. Base case: $$T(1)=c=2\cdot 1-\lg(1)-2+1c$$

Inductive case: Fix $$k$$ and assume the claim holds for smaller values. Now

$$
T(k)=\lg(k)+2T(\frac{k}{2}) \\
=\lg(k)+2[2(k/2)-\lg(k/2)-2+(k/2)c] \\
=\lg(k)+2[k-(\lg(k)-1)-2+(k/2)c] \\
=\lg(k)+2k-2(\lg(k)-1)-4+kc \\
=-\lg(k)+2k-2+kc \\
$$

### Scratchwork

(From Demo 1, the answer will be $$T(n)=2n-\lg(n)-2+nc$$)

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

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


### Solution

$$
\begin{align*}
T(n)&={\color{red} 1\lg(n)-0+2T(\frac{n}{2})} &(k=1)\\
&=\lg(n)+2[\lg(\frac{n}{2})+2T(\frac{n}{4})] \\
&=\lg(n)+2[\lg(n)-1+2T(\frac{n}{4})]\\
&={\color{red} 3\lg(n)-2+4T(\frac{n}{4})} &(k=2)\\
&=3\lg(n)-2+4[\lg(\frac{n}{4})+2T(\frac{n}{8})]\\
&=3\lg(n)-2+4[\lg(n)-2+2T(\frac{n}{8})]\\
&={\color{red} 7\lg(n)-10+8T(\frac{n}{8})} &(k=3)\\
\end{align*}
$$

Guess the pattern: 

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

Choose $$k$$ such that $$T(\frac{n}{2^k})=T(1)=c$$, namely $$k=\lg(n)$$.

$$
(2^k-1)\lg(n)-(2+(k-2)2^{k})+2^kT(\frac{n}{2^k}) \\
=(n-1)\lg(n)-(2+(\lg(n)-2)n)+nc \\
=2n-\lg(n)-2+nc \\
$$