# 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?

$$T(n)=T(1+f_3(n-2))+T(n-2),\\T_0=T_1=1.$$
• 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. Feb 13 at 17:40
• 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 Feb 13 at 18:11
• @complexity: how to you get this $O$ answer ? Feb 13 at 19:50