Сложность по времени для рекуррентного отношения T (n) = T (n-1) * n

Question

Мне нужна помощь со следующим отношением повторений.

T (1) = 1

T (n) = T (n-1) * n

Это то, что я пробовал. Я думаю, что я мог испортить часть замещения, но, пожалуйста, еще раз, пожалуйста, посмотрите, дайте мне знать, если сложность времени у меня правильная.

T(n) = T(n-1)*n               T(n-1) = T(n-2)*n-1
T(n) = [T(n-2)*(n-1)]*n
T(n) = T(n-2)*(n-1)*n
T(n) = [T(n-3)*n-2]*(n-1)*n
T(n) = T(n-3)*(n-2)*(n-1)*n
...
...
...
T(n) = T(n-k)*(n-(k-1))*(n-(k-2))...*(n-1)*(n)

Assuming n-k=0, n=k

T(n) = T(n-n)*(n-n+1)*(n-n+2)...*(n-1)*(n)
T(n) = T(0)*(1)*(2)...*(n-1)*n

O(n^2)

Теперь я не уверен, что то, что я сделал, былоточно правильно или нет, но любая помощь будет оценена.

Answer 1

Только последняя сложность неверна, в итоге вы получите O (n!).

Рекурсивное отношение должно быть T (n) = T (n-1) + n для получения O (n ^2) как сложность.

Answer 2

Очень близко! Вы правильно определили, что сложность составляет

n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Однако это не O (n ² ). Было бы O (n ² ), если бы вы добавили условия вместо умножения их.

Что вы называете произведением всехнатуральные числа от 1 до n включительно?