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

Question

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?

Yves Daoust · Accepted Answer · 2023-02-13 13:39:22Z

1

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.

answered Feb 13 at 13:39

Yves Daoust

8,84114 silver badges39 bronze badges

$\begingroup$ 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. $\endgroup$
– complexity
Feb 13 at 17:40
$\begingroup$ @complexity: who told you that this answer is wrong ? The solution is virtually in front of your eyes, please read again. $\endgroup$
– Yves Daoust
Feb 13 at 17:43
$\begingroup$ 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 $\endgroup$
– complexity
Feb 13 at 18:11
$\begingroup$ @complexity: how to you get this $O$ answer ? $\endgroup$
– Yves Daoust
Feb 13 at 19:50

Add a comment |

1 Answer 1