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.


2 Answers 2


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.