Calculation of Run time

Question

Given is the folowing recurrence relation: $$ T(n) = 2 \cdot T\left(\frac{n}{4}\right) + \sqrt{n} \cdot \log_2 n $$

Master theorem cannot be applied here for calculation of run time.

How can I do it instead?

Answer 1

Hint:

Let us define $T(n)=T(4^m)=S(m)$.

Then

$$T(4^m)=2T(4^{m-1})+\sqrt{4^m}\log_2(4^m)$$

or

$$S(m)=2S(m-1)+2m2^m,$$ which is a linear recurrence.

As the characteristic equation has the root $m=2$, the solution should be of the form

$$S(m)=(am^2+mb+c)2^m$$

i.e.

$$T(n)=(a\log_4^2n+b\log_4n+c)\sqrt n.$$

(The basis of the logarithm is immaterial.)