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
On
We use the iteration method to find an explicit form. Given the recurrence:
$$ T(n) = 3T\left( \frac{n}{3} \right) + \log_3 n $$
we expand, getting:
$$ T(n) = \log_3 n + 3 \log_3 \frac{n}{3} + 3^2 \log_3 \frac{n}{3^2} + 3^3 \log_3 \frac{n}{3^3} + ... + 3^{\log_3 n} \log_3 1 $$
From which we conclude:
$$ T(n) = \sum_{k = 0}^{\log_3 n} 3^k \log \frac{n}{3^k} $$
We can reformulate, getting:
$$ T(n) = \sum_{k = 0}^{\log_3 n} 3^k \log_3 n - \sum_{k = 0}^{\log_3 n} k \cdot 3^k $$
Computing the sums of the series gives:
$$ T(n) = \log_3 n \left( \frac{3n - 1}{2} \right) - \frac{3}{4} \left( 1 - (1 + \log_3 n)n + 3n \log_3 n \right) $$ $$ = \frac{3n}{2} \log_3 n - \frac{1}{2} \log_3 n - \frac{3}{4} + \frac{3}{4} \left( n + n \log_3 n \right) - \frac{9}{4} n \log_3 n $$ $$ = \frac{3}{4}n - \frac{1}{2} \log_3 n - \frac{3}{4} $$
And so we have found an explicit form for the recurrence. We verify its validity using induction:
$$ T(n) = 3T\left( \frac{n}{3} \right) + \log_3 n $$ $$ = 3\left( \frac{3}{4} \frac{n}{3} - \frac{1}{2} \log_3 \frac{n}{3} - \frac{3}{4} \right) + \log_3 n $$ $$ = \frac{3}{4} n - \frac{3}{2} \log_3 \frac{n}{3} - \frac{9}{4} + \log_3 n $$ $$ = \frac{3}{4} n - \frac{3}{2} \left( \log_3 n - 1 \right) - \frac{9}{4} + \log_3 n $$ $$ = \frac{3}{4}n - \frac{1}{2} \log_3 n - \frac{3}{4} $$
And so we have verified the bound. This means $T(n) = \Theta(n)$.
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)$.