Solving $T(n) = 2T(\frac{n}{4}) + \log n$

Question

Solve following recursive relation $T(n) = 2T(\frac{n}{4}) + \log n$ without resorting to the master theorem. I've tried substitution method but it didn't work. I don't know whether there is a method using calculus for solving problems like this. According to WA, the answer is $T(n)\in \Theta(\sqrt n)$.

After substitution, I've found that $$T(n) = 2^iT(\frac{n}{2^{2i}}) + \sum_{k=0}^{i-1} 2^k\log(\frac{n}{2^{2k}})$$

and don't know how to proceed further.

Answer 1

Let's write $s = \frac{1}{2}\log n$, so that it suffices in order to conclude to bound the sum $$ \sum_{k=0}^{s-1} 2^k \log\frac{2^{2s}}{2^{2k}}= 2\sum_{k=0}^{s-1} (s-k)2^k\tag{1} $$ (plugging $i=s$ in the formula you obtained, as the first term $2^sT(n/2^{2s})$ then becomes $O(\sqrt{n})$. We then have, from (1), $$ \sum_{k=0}^{s-1} (s-k)2^k = \sum_{\ell=1}^s \ell \cdot 2^{s-\ell} = 2^s \sum_{\ell=1}^s \ell \cdot 2^{-\ell} \leq 2^s \sum_{\ell=1}^\infty \ell \cdot 2^{-\ell} = O(2^s) = O(\sqrt{n}) \tag{2} $$ the second-to-last equality since the sum $\sum_{\ell=1}^\infty \ell \cdot 2^{-\ell}$ converges (and therefore is an absolute constant), and the last by definition of $s$.

Answer 2

In $T(n) = 2T(\frac{n}{4}) + \log n $, let $n = 4^m$. This becomes $T(4^m) = 2T(\frac{4^m}{4}) + \log (4^m) = 2T(4^{m-1}) + m\log 4 $.

Divide this by $2^m$ to get $\dfrac{T(4^m)}{2^m} = \dfrac{2T(4^{m-1}) + m\log 4}{2^m} = \dfrac{T(4^{m-1})}{2^{m-1}}+\dfrac{m\log 4}{2^m} $.

Writing $U(m) =\dfrac{T(4^m)}{2^m} $, this becomes $U(m) =U(m-1)+\dfrac{m\log 4}{2^m} $.

This now telescopes, so you need to get $U(n)-U(0) =\sum_{m=1}^n \dfrac{m\log 4}{2^m} $.

Then you can work backwards to get $T(4^m)$.