I'm confused on how to prove the below using induction:
T(n) = 3T(n/9) + √n
I have been given the base case T(1) = 1. I know using the master theorem that the time complexity is O(√n log n). However, when trying to find the inductive hypothesis (function form) of the recurrence by substituting k = 0, 1, 2, 3... into T(9^k), I'm not sure how to find the function form.
Thanks!