Consider an algorithm which has the following structure
function f(n) is
if n > 1 then
stmt // "statement" - takes Theta(1)
f(n/3)
f(n/3)
f(n/3)
else
stmt // takes Theta(1)
end-if
end-function
Looking at this algorithm I can see that the corresponding recurrence relation looks like this:
$$ T(n) = \begin{cases} 1 & n \leq 1 \\ 1 + 3T(n/3) & n > 1 \\ \end{cases} $$
I hope the above is correct. I am trying to find this complexity. First I assume that $n = 3^k, k \in \mathbb{N}$.
We can do a few calculations to observe a pattern.
$T(n) = 1 + 3T \bigg( \frac{n}{3} \bigg)$
$T \bigg ( \frac{n}{3} \bigg ) = 1 + 3T \bigg ( \frac{n}{9} \bigg )$
$T \bigg ( \frac{n}{9} \bigg ) = 1 + 3T \bigg ( \frac{n}{27} \bigg )$
...
$T(1) = 1$
So then
$$T(n) = 1 + 3T \bigg ( \frac{n}{3} \bigg )$$
$$= 1 + 3 \bigg (1 + 3T \bigg ( \frac{n}{9} \bigg ) \bigg ) = 1 + 3 + 9T \bigg ( \frac{n}{9} \bigg )$$
$$= 1 + 3 + 9 \bigg (1 + 3T \bigg ( \frac{n}{27} \bigg ) \bigg ) = 1 + 3 + 9 + 27T \bigg ( \frac{n}{27} \bigg )$$
Now we can notice the pattern. By induction we can prove that the complexity is
$$T(n) = 1 + 3^1 + 3^2 + ... + 3^{k - 1} + 3^kT \bigg ( \frac{n}{3^k} \bigg )$$
Since we made the assumption that $n = 3^k$ we can say that the last term from above, namely $T(n/3^k)$ is equal to $1$. So the above sum is:
$$T(n) = 1 + 3^1 + 3^2 + ... + 3^k$$
This is a geometric series, so we can find the sum:
$$T(n) = \frac{3^{k + 1} - 1}{3 - 1} = \frac{3 ^ {k + 1} - 1}{2}$$
Now if we replace with the assumption we made at the start (that $n=3^k$) we get:
$$T(n) = \frac{3n - 1}{2}$$
So then we can conclude that $T(n) \in \Theta(n)$.
The problem I have with the above result is that it doesn't seem intuitive. Since at each step we divide $n$ by $3$ I would expect the final complexity to be $\Theta(\log_3 n)$ (call it $\Theta(\log n)$ if you want, you get the point). But in my calculations I didn't get that. So are my calculations wrong or is my intuition wrong? If my calculations are wrong, why and how should I solve these mistakes?