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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.