- #1

- 158

- 23

T(n) =

\begin{cases}

2 & \text{if } n = 2 \\

2T(\frac{n}{2})+n & \text{if } n = 2^k \text{, for } k > 1

\end{cases}\\ \text{ }

\\ \text{ }

\\ \text{ }

\\

\text{Prove } T(n) = n\lg(n) \text{ if } n = 2^k\text{, for } k > 1.

$$

I am crawling through the "Introduction to Algorithms" textbook, in preparation for a future course, and this question has stumped me. I was able to understand proving algorithmic correctness using loop invariants, but I don't have a lot (any) experience in proofs. As a side-note, lg(n) is the binary logarithm of n. Also: The book did not make it explicit, but k is above 1 and an integer.

Here is what I have so far.

**Base case**

$$

\begin{align}

\text{Let } n = 2^k \text{ where } k &= 2 \text{ (minimal case)}\\

n &= 2^k = 4\\

2T(\frac{n}{2}) + n &= n\lg n\\

2T(2) + 4 &= 4\lg 4\\

2*2 + 4 &= 4*2\\

8 &= 8

\end{align}

$$

**Inductive hypothesis**

$$

T(2^{k+1}) = 2^{k+1}\lg{2^{k+1}}

$$

**Inductive step**

$$

2T(\frac{2^{k+1}}{2}) + 2^{k+1} = 2^{k+1}(k+1)

$$

Beyond that, I cannot go. I would greatly appreciate any hints.

(I reiterate... this is not homework, I'm trying to solve this as a personal challenge)