Question: Show by induction that any solution to a recurrence of the form
T(n) ≤ 2T(n/3) + c log3 n
is O(n log3 n). What happens if you replace 2 by 3 (explain why)? Would it make a difference if we used a different base for the logarithm (only an intuitive explanation is needed here)?