Solving recurrence relations using master's theorem

Question

Can we solve following recurrence relation using Master's theorem-

$T(n)=T(n/2)+\log n$

The thing to notice here is that, do $n (n^{\log b} a)$ and $\log n (f(n))$ have an exponential difference?

Answer 1

It seems the following.

It seems that Master’s Theorem is not applicable here, because none of its three conditions is satisfied.

We may search a recurrence solution as follows. Let $n=2^k$. Then $k=\log_2 n$, $T(n)=R(k)$ and

$$R(k)=R(k-1)+\log 2^k= R(k-1)+k\log 2.$$

So $R(k)\sim \frac{k(k+1)}2\log 2$ and $T(n)\sim \frac{\log_2 n(\log_2 n+1)}2\log 2.$