I just can't solve this problem, I'm new to reccurences. I have this recurrence


The second term will be:


And so on.

It's complexity is O(n!) but i don't know how to solve it.

I hope you can help me with an idea!

  • 1
    $\begingroup$ First, be clear about what you mean by "complexity of a recurrence relation". Do you simply want to solve the recurrence, or determine the computational cost of evaluating it (naively following the definition)? $\endgroup$ – Raphael Jun 25 '15 at 23:52

Hint: Prove by induction on $n$ that $T(n) = n!$.

Note that a recurrence relation doesn't have a complexity. Rather, it defines a function. In many cases, this function is the running time of some algorithm, and then the time complexity of the algorithm is the solution to the recurrence.

| cite | improve this answer | |
  • $\begingroup$ If we're being careful about terminology, algorithms don't have a complexity but running time. Complexity is a property of problems. $\endgroup$ – David Richerby Jun 25 '15 at 21:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.