CODEWITHSUNDEEP
algorithmmath
nathan
nathan

Reputation: 844

recursion time complexity calculation

Everyone. I have quick question about one recurrence: T(n) = n^2 * T(n-1).

I am using "recursion-tree method" of CLRS, and got

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

I don't know how to summarize this expression to a upper bound. Could some one help here

Upvotes: 0

Views: 59

Answers (1)

meowgoesthedog
meowgoesthedog

Reputation: 15035

You seem to be overcomplicating things. If T(n) = n^2 * T(n - 1) is correct, you would simply have a product of squares:

enter image description here

(assuming the stopping condition is n = 1).

Upvotes: 1

Related Questions