Issue in calculating the complexity of a recursive algorithm

34 Views Asked by At

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?