ā“ Question

Use mathematical induction to show that when n ≄ 2 is an exact power of 2, the solution of the recurrence:

$T(n)=\begin{cases} 2 & if n = 2,\\ \\ 2T(n/2) + n & if n > 2. \end{cases}$

is

$T(n) = n lg n$

šŸ’” Answer