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 T(n) = cn k=0 is a solution to the above recursion using induction (c) Show that T(n) - O (n ((Hint: use the geometric series formula.) (d) Show that n (j)10g4(n) = nlog