# Time complexity of function

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.

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)$$.

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}$$