1. Use mathematical induction to show that when n is a power of 2, T(n) = n lg n is the solution of the recurrence relation T(n) = ( 2 if n = 2 2 · T( n 2 ) + n if n […]