Пространственная сложность рекурсивной функции (Time & Space)

Question

Ниже приведена функция рекурсии, и я не рассчитал сложность времени и пространства.Я посмотрел на некоторые ресурсы, но мне не хватило понимания.Может ли кто-нибудь объяснить способ решения простейшим образом и ответить на вопрос?

Кстати, я попытался решить сложность времени и нашел O (2 ^ n).Это правильно?

int func(int n) { 
     if (n < 3)
         return 3;
     else {
         return func(n-3)*func(n-3);
     }
}

Answer 1

Да, сложность времени действительно O(2 ^ n).

Отношение повторения для сложности времени: T(n) = 2 * T(n - 3)

Применение приведенного выше уравнения k раз: T(n) = 2 * 2 * 2 ... k times * T(n - 3 * k) = 2 ^ k * T(n - 3k)

Когда k равен n/3, T(n) = 2 ^ k = 2 ^ (n / 3) = O(2 ^ n)

За один раз выполняется только одна функция, а глубина стека может составлять k при макс.Итак, сложность пространства составляет n / 3 или O(n)