Сложность рекурсивной функции

Question

У меня есть рекурсивная функция, и я пытаюсь понять ее сложность.обозначим P (n) - время выполнения функции (если задан параметр n).Я знаю, что: P (n) = n + (n-1) * P (n-1) [p (1) = 1]

Как я могу выразить P (n) без использования P (...)?

Answer 1

Это было бы O (n ⁿ ).Обратите внимание, что если вы начнете расширять выражение, вы получите элемент с мощностью n, увеличенной на 1 на каждой итерации.Это будет доминирующий элемент, поэтому другие могут быть отброшены для вычисления O ().Для более формального решения см. Ссылку, предоставленную @ Max.