Может ли кто-нибудь объяснить мне, как это продемонстрировать,
T (n, d) ≤ T (n - 1, d) + O (d) + d / n (O (dn) + T (n - 1, d - 1))
решается как
T (n, d) ≤ bnd! (b - константа)
с использованием метода подстановки?
Я сделал это, но не знаю, правильно ли это.
- T (n -1, d) ≤ b (n-1) d!
- O (d) ≤ bd
- d / n (O (dn) + T (n - 1, d - 1 )) ≤ d / n (bnd + b (n-1) d (n-1)!)