0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\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
    Commented Feb 13, 2023 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$
    – user16034
    Commented Feb 13, 2023 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
    Commented Feb 13, 2023 at 18:11
  • $\begingroup$ @complexity: how to you get this $O$ answer ? $\endgroup$
    – user16034
    Commented Feb 13, 2023 at 19:50

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.