ā 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$
Chapter Two - Exercise 2.3-4
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$