Solution to recurrence relation for $T(n)=3T(\frac{n}{2}) + \log n$

51 Views Asked by Bumbble Comm At 28 Mar 2026 - 4:13

I have a recurrence relation,

\begin{align} T(n) & = 1\quad \text{if }n = 1 \\ & = 3T(n/2) + \log_2n \;\; \text{otherwise} \end{align}

Now on going with recurrence tree method, I ended with following calculations.

Is it the correct answer? Or should it be rounded to $\Theta(n^2 log\,n)$? Or something else?

I am slightly stuck at calculations so a help on them would be very nice.