recurrence relation using master method

Question

I know that the Master theorem is used for the recurrence relations of the form: $$T(n)=aT(n/b)+f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master theorem: $$T(n)=T(n/4)+n^{1/2}+5$$ $$T(1)=3$$ What should I do? Thanks.

Answer 1

I think a nice way to deal with such a recurrence is to define a new sequence $U_k$:

$$T\left(4^k\right) = U_k$$

that satisfies

$$U_k - U_{k-1} = 2^k + 5$$

$$U_0=3$$

This is a linear, inhomogeneous recurrence relation with general solution

$$U_k = A \cdot 2^k + B k +C$$

Plugging back into the equation and applying the initial condition, we find that

$$U_k = 2^{k+1} + 5 k + 1$$

which means that, using $T(n) = U_{(\log_2{n})/2}$

$$T(n) = 2 \sqrt{n} + \frac{5}{2} \log_2{n} + 1$$