Сегодня в классе мой учитель написал на доске этот рекурсивный факториальный алгоритм:

int factorial(int n) {
   if (n == 1) 
       return 1;
   else 
       return n * factorial(n-1);
}

Она сказала, что это имеет стоимость.T(n-1) + 1

Затем с помощью итерационного метода она сказала, чтоT(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, поэтому алгоритм останавливается, когдаn - j = 1, так .j = n - 1

После этого она заменилаj вT(n-1) + 1и получил.T(1) + n-1

Она прямо сказала, что для этого n-1 = 2(log2п-1), поэтому стоимость алгоритма является экспоненциальной.

Я действительно потерял два последних шага. Может кто-нибудь объяснить мне их?