Proving T(n) = 3T(n/9) + n^1/2 using induction

Question

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!

Answer 1

$$\begin{align}T(9^4)&=3T(9^3)+3^4 \\&=3(3T(9^2)+3^3)+3^4=3^2T(9^2)+2\cdot3^4 \\&=3^2(3T(9)+3^2)+2\cdot3^4=3^3T(9)+3\cdot3^4 \\&=3^3(3T(1)+3^1)+3\cdot3^4=3^4T(1)+4\cdot3^4 \end{align}$$

and we can infer

$$T(9^m)=3^m(T(1)+m),$$ which is

$$T(n)=\sqrt n(T(1)+\log_9(n)).$$

---

Verification:

$$\begin{align}\sqrt n(T(1)+\log_9(n))&=3\sqrt{\frac n9}\left(T(1)+\log_9\left(\frac n9\right)\right)+\sqrt n \\&=\sqrt n(T(1)+\log_9(n))-\sqrt n+\sqrt n\end{align}$$

is indeed an identity.

Answer 2

Other method:

We divide both membres by $\sqrt n$:

$$\frac{T(n)}{\sqrt n}=\frac{3T\left(\dfrac n9\right)}{\sqrt n}+1=\frac{T\left(\dfrac n9\right)}{\sqrt{\dfrac n9}}+1.$$

This is of the form

$$S(n)=S\left(\frac n9\right)+1$$ and denotes the number of times you can divide by $9$ before reaching $1$, or $$\log_9(n)+S(1).$$