Доказательство сложности рекурсивного определителя

Question

Я хочу доказать, почему определитель Лапласа или сложность рекурсивного алгоритма n!. Кто-нибудь может доказать это для меня? Я не знаю, как это могло тогда быть n!, учитывая, что уравнение T(n)=nT(n-1)+3n-1 включает только умножение и сложение.

Answer 1

Попробуйте расширить:

T(n) = n T(n-1) + 3n-1 = 
       n ((n-1)T(n-2) + 3(n-1)-1) + 3n-1 =
       n (n-1) T(n-2) + 3 n (n-1)  - n + (3n - 1)

Теперь по индукции вы можете показать, что (если T(1) = 1):

T(n) = n (n-1) (n-2) ... 1 + 3(n + n (n-1) + ... + n!) - 
      (1 + n + n (n-1) + ... + n (n-1) ... n * (n-1) * ... * (n-2)) 
     = Theta(n!)