Consider the recurrence

2. Consider the recurrence T(1) = c, T(n)-5T(n/4) + cn for n > 1 (a) Use the Master Theorem to get the Big-O class of T(n). (b) Prove that rin).cn. ,(1) e) Show that T)) (Hint: use the geometric series formula.) (d) Show that )nlog(5) is a solution to the above recursion using induction Show that T(n)=O(n (1)",("') (Hint: use the gr