recursion time complexity calculation

Question

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

Double check: is the * in T(n) = n^2 * T(n-1) supposed to be a * or a +? — chux
– chux, Commented Sep 15, 2018 at 18:00
@chux 1. it is * not + ] 2. u r right, that is what "CLRS" means — nathan
– nathan, Commented Sep 15, 2018 at 18:13

meowgoesthedog · Accepted Answer · 2018-09-15 21:33:05Z

1

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

(assuming the stopping condition is n = 1).

edited Sep 15, 2018 at 21:33

answered Sep 15, 2018 at 18:18

meowgoesthedog

15.1k4 gold badges30 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

nathan Over a year ago

sir, could you tell me how n square * (n-1) square ... * t(1)square is summarized to n! square. many thanks

meowgoesthedog Over a year ago

@nathan because multiplication is commutative. So if you have two square numbers a^2 * b^2 you can write them as (a * b)^2. It follows that n^2 * (n - 1)^2 * (n - 2)^2 ... can be written as [n * (n - 1) * (n - 2) ...]^2, and of course n * (n - 1) * (n - 2) ... is defined to be n!.

nathan Over a year ago

opps, I can't remember this math. Thanks a lot

Collectives™ on Stack Overflow

recursion time complexity calculation

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related