Time complexity of function

Question

int q(int n)
{
        if (n <= 0) return 0;
        return 1-q(q(n-1));
}

I'm not sure how to approach this. I tried representing the time complexity as a function $T(n)$ and then use repeated substitutions: So I got $T(n)=C+T(T(n-1))$ where $C$ is a constant representing a constant amount of lines we have in the function. Using repeated substitution we get: $T(n)=C+T(C+T(...T(C+T(0))))$, but $T(0)=0$ so $T(n)=C+T(C+T(...T(C)))$ and now we got a function that is only dependent on $C$ which is a constant, but I don't know how to continue from here.

Answer 1

First observe $q(n)$ always returns either $0$ or $1$. This can be proven formally by induction.

If $n \le 0$ this is immediate. If $n=1$ then the return value is $q(q(0)) = 1-q(0) = 1$. Suppose now that the claim holds up to some $n \ge 1$ and consider $q(n+1)$. The return value is $1-q(q(n))$ which is either $1-q(0)=1$ or $1-q(1)=0$.

You can now bound the time complexity of your function. Let $T(n)$ be the time spent by $q(n)$. If $n \le 1$, $T(n)$ is a constant. Otherwise the following recurrence relation holds: $$ T(n) = T(n-1) + \Theta(1), $$ where $T(n-1)$ accounts for the time spent computing $q(n-1)$ and the constant additive term accounts for time needed by the outer call to $q$ (which is either $q(0)$ or $q(1)$) and all other operations.

This recurrence has solution $T(n) = \Theta(n)$.

Answer 2

You can do these observations:

• $n\le 0\to q(n)=0$;

• $n=1\to q(n)=1-q(q(0))=1-q(0)=1$;

• $n=2\to q(n)=1-q(q(1))=1-q(1)=0$;

• $n=3\to q(n)=1-q(q(2))=1-q(0)=1$;

• $n=4\to q(n)=1-q(q(3))=1-q(1)=0$;

• $\cdots$

The pattern is obvious. From this, a call for $n>0$ involves $2n$ recursive calls of which one is made with argument $0$ or $1$, thus in constant time. So if all elementary operations are done in constant time,

$$T(n)=\begin{cases}n\le0\to c&=\Theta(1) \\n>0,\text{odd }\to an+b&=\Theta(n) \\n>0,\text{even}\to an+b'&=\Theta(n). \end{cases}$$