How to solve this recurrence relation using substitution method


Can anyone explain to me how to demonstrate that,

T (n, d) ≤ T (n − 1, d) + O(d) + d/n (O(dn) + T (n − 1, d − 1))

is solved by

T (n, d) ≤ bnd! (b is a constant)

using the substitution method?

I have done this but I don’t know if it is correct.

  • 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)!)