Тета время выполнения рекурсии

Question

Как рассчитать время исполнения Theta для данного кода:

void f(int n)
{
    for (int i=3; i<n; ++i)
        for (int j=0; j<i; ++j)
            f(n-1);
}

Пока что я получил это, но я не знаю, правильно ли это или как перенести это в тета-нотацию.

f(n) = n^2 * f(n-1)
f(n) = n^2 * (n-1)^2 * f(n-2)
f(n) = n^2 * (n-1)^2 * (n-2)^2 * f(n-3) 
...

Answer 1

Поскольку каждый вложенный цикл for имеет сложность O(N^2), и каждый раз, когда вы вызываете функцию внутри другой функции, сложность умножается, в результате вы получаете O((N!)^2), где N также количество раз, которое вы повторяете. Это конечно потому что N! = N*(N-1)*(N-2)*...*(N-N+1)и все значения, используемые для создания факториала, возводятся в квадрат.

Answer 2

Если мы заменим эти 3 на ноль (что, очевидно, ничего не меняет в Θ), мы можем очень легко получить точное количество вызовов функций:

Θ_{f (1)} = 1
Θ_{f (n)} = n² Θ Θ_{f (n-1)} ∀ n > 0

Итак, используя коммутативность продукта,

_{н н н н}
Θ_{f (n)} = ∏ j ² = ∏ j ⋅ ∏ j = n! ⋅ н!
я = 1 я = 1 я = 1
= (n!)²

Как сказал Джейсон.