Using of substitution method

Question

I am learning that how recurrences solve and I try to use substitution method in this question:

$$T(n) = 3T(n/2) + n^2$$

What should be my guess ?

Answer 1

Enforce $n \mapsto 2^n$. We have,

$$T(2^n)=3T(2^{n-1})+4^n$$

Now define $f(n)=T(2^n)$. So that now we have,

$$f(n)=3f(n-1)+4^n$$

This is a more standard problem now.

Note,

$$4^{n+1}=3(4^{n})+4^n$$

Subtracting this from the previous equation gives,

$$f(n)-4^{n+1}=3(f(n-1)-4^n)$$

$$g(n)=3g(n-1)$$

With $g(n)=f(n)-4^{n+1}$.

So,

$$g(n)=g(0)3^n$$

Now we unwind our substitutions.

$$f(n)=g(0)3^n+4^{n+1}$$

$$T(2^n)=g(0)3^n+4^{n+1}$$

We also have $g(0)=f(0)-4=T(1)-4$.

So,

$$T(2^n)=(T(1)-4)3^n+4^{n+1}$$

Or if you wish, with the substitution $n \mapsto \frac{\ln n}{\ln 2}$:

$$T(n)=(T(1)-4)3^{\frac{\ln n}{\ln 2}}+4n^2$$