Как рассчитать временную сложность этой рекурсии?

Question

Я заинтересован в расчете времени и пространства следующего кода, но, похоже, мне это очень тяжело. Я знаю, что самая глубокая рекурсия может быть достигнута n, поэтому пространство должно быть O (n). Однако я не знаю, как рассчитать сложность времени ... Я не знаю, как написать формулу, когда речь идет о рекурсиях, подобных этим формам, например: f(f(n-1)). если это было что-то вроде return f3(n-1) + f3(n-1), то я знаю, что это должно быть O (2 ^ n), поскольку T (n) = 2T (n-1) правильно?

Вот код:

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

Спасибо за вашу помощь!

Answer 1

Обратите внимание, что f3(n) = n - 1 для всех n, поэтому вычисляется строка f3(1 + f3(n-2)), сначала f3(n-2), которая возвращает n - 3, а затем f3(1 + n - 3) = f3(n-2) вычисляется снова!
Итак, f3(n) вычисляет f3(n-2) дважды, вместе с некоторыми издержками O(1).
Мы получили формулу рекурсии T(n) = 2T(n-2) + c для некоторой константы c, а T(n) - время выполнения f3(n).
Решая рекурсию, получаем T(n) = O(2^(n/2)).