Find a tight bound for the following recurrence.
$$T(1) = 2$$ $$T(n) = T(\frac{n}{3}) + 4n$$
Using the master's theorem, I have:
$$ 1 > \log{_3}{1}$$
$$k > \log{_b}{a}$$
Thus, I can conclude that $T(n) = O(n^k)$
The problem is that this seems conflicting with what I've found using substitution method.
$k = 1$ $$T(n) = T(\frac{n}{3}) + 4n$$ $k = 2$ $$T(n) = T(\frac{n}{9}) + 8n$$ $k = 3$ $$T(n) = T(\frac{n}{27}) + 12n$$ $k = 4$ $$T(n) = T(\frac{n}{81}) + 16n$$
Guessing the recurrence, I get the following
$$T(n) = T(\frac{n}{3^k}) + 4kn$$
At the base case, $\frac{n}{3^k} = 1$, thus, $n = 3^k$, and therefore, $ k = \log{_3}{n}$
Then, we have
$$T(n) = T(1) + 4n\log{_3}{n}$$ $$T(n) = 2 + 4n\log{_3}{n}$$
Doing some calculations, I can conclude that $T(n) = \theta(n\log{_3}{n})$. This causes conflict with the answer I reached from the master's theorem.
What did I do wrong?