# Complexity of recursive function that calls itself with it's own return value

Given the following code:

int f3(int n)
{
if(n <= 2) return 1;
f3(1 + f3(n-2));
return n - 1;
}


I was trying to find the time complexity and I got this expression: $$T(n)=1+T(T(n-2))$$ which I've never seen before.

I know the answer is $$O(2^{\frac{n}{2}})$$ but I have no idea how to get there. Can anyone explain the calculation process?

Hint:

The correct recurrence is

$$T(n)=T(1+f_3(n-2))+T(n-2),\\T_0=T_1=1.$$

That should be easier to solve.

• Thank you for commenting. I was trying to work it from here, but I keep getting the same wrong answer ($O(\frac{n}{2})$). I think that the problem is that I've never seen this type of recursion. If you could give some more explanation it would be much appreciated. Commented Feb 13, 2023 at 17:40
• @complexity: who told you that this answer is wrong ? The solution is virtually in front of your eyes, please read again.
– user16034
Commented Feb 13, 2023 at 17:43
• This problem is taken from a previous test at my university, and the official answer there is $O(2^{\frac{n}{2}})$, and when I try to calculate myself I get $O(\frac{n}{2})=O(n)$. So it is either I'm missing something, or one of the answers is wrong Commented Feb 13, 2023 at 18:11
• @complexity: how to you get this $O$ answer ?
– user16034
Commented Feb 13, 2023 at 19:50