3
$\begingroup$

$$\begin{align*} &T(n) = 2T(n/2) + \log_2(n)\\ &T(1) = 0 \end{align*}$$

$n$ is a power of $2$

solve the recurrence relation

my work so far:

unrolling this, we have

$$\begin{align*} T(n) &= 4T(n/4) + \log_2(n) -1\\ &= 8T(n/8) + 2\log_2(n) -2\\ &=\log_2(n-1) \log_2(n) - \log_2(n) + 1 \end{align*}$$

after substituting for base case.

where is my mistake?

2 Answers 2