CODEWITHSUNDEEP
complexity-theory
Belgi
Belgi

Reputation: 15052

Complexity of a recursive function

I have a recursive function, and I'm trying to figure out it's complexity. denote P(n) - the runtime of the function (when given the parameter n). I know that : P(n)=n+(n-1)*P(n-1) [p(1)=1]

How can I express P(n) without using P(...) ?

Upvotes: 1

Views: 297

Answers (1)

SomeWittyUsername
SomeWittyUsername

Reputation: 18348

That would be O(nn). Notice that if you start expanding the expression, you'll get an element with power of n increased by 1 on each iteration. This will be the dominant element so others can be dropped for the O() calculation. For a more formal solution see the link provided by @Max.

Upvotes: 1

Related Questions