Give tight asymptotic bounds for the following recurrence. Justify your answers by
working out the details or by appealing to a case of the master theorem
$$T(n) = 3T\left(\frac n3\right)+\log(n)$$
I choose master's theorem to solve this recurrence
$a=3$, $b=3$ , $f(n)=\log(n)$ —> stuck here
how can handle this recurrence to solve it by master theorem or is there other way to solve it without master theorem
Best Answer
You have that (among other things) $\log(n) \in O \left (n^{0.5} \right )$. Since $0.5<\log_b(a)=\log_3(3)=1$, the first case of the master theorem tells you that $T(n) \in \Theta(n)$.