❓ 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$
Comments
powered by giscusComments are GitHub Discussions threads. Sign in with your GitHub account to leave a comment, react, or reply.