4.3-4

Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition T(n) for recurrence (4.19) without adjusting the boundary conditions for the inductive proof. $$ T(n) = 2 T( \lfloor n/2 \rfloor) + n $$ let $ T(n)\leq c_1 n lgn +c_2 n $ $$ T(n) \leq 2 c_1 n/2 lg(n/2) + 2 c_2 n/2 $$ $$ T(n) \leq c_1 n lg(n/2) + c_2 n $$ $$ T(n) \leq c_1 n lg n - c_1 n + c_2 n $$ $$ T(n) \leq c_1 n lg n - ( c_1 n - c_2 n ) $$ $$ c_1 n - c_2 n \geq 0 $$ $$ c_1 \geq c_2 $$ for base case $ T(1)\leq c_1 1 lg1 +c_2 1 $ $ T(1)\leq c_2 1 $ if $c_2$ is sufficiently large the above case is proved for base case as well.