Solve the recurrence relation $T(n)=2T(n/2)+\log(n)$ given that $T(1) = 1$

Question

Question:

Assume that a recurrence relation is given as below:

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

and we know that $T(1) = 1$

We want to solve the relation (find an explicit definition of $T(n)$ which does not rely on itself).

My solving:

I wanted to solve it using substitution method but when i tried I get the series $$\log(n)+2\log(n/2)+4\log(n/4)+8\log(n/8) ... 2^k\log(n/2^k)$$ which I am not able to solve.

Answer 1

Assuming $\log(n) = \log_2 n$ we have

$$ T\left(2^{\log_2 n}\right) = 2T\left(2^{\log_2 \frac n2}\right)+\log_2 n $$

now calling $\mathcal{T}(\cdot) = T\left(2^{(\cdot)}\right)$ and $z = \log_2 n$ we follow with the linear recurrence

$$ \mathcal{T}(n) = 2\mathcal{T}(z-1) + z $$

with solution

$$ \mathcal{T}(n) =2^{z-1}c_0 + 2^{z+1}-(z+2) $$

and now going backwards with $z = \log_2 n$ we arrive at

$$ T(n) = \frac n2 c_0 +2(n-1)-\log_2 n $$

Finally with $T(1) = 1$ follows $c_0 = 2$

Answer 2

The recurrence relation is not well defined. You can't calculate, for example, $T(3)$.