Recurrence Relation

Question

Why is the recurrence relation of recursive factorial algorithm this?

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

Why is it not this?

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

Putting values of n i.e 1,2,3,4...... the second recurrence relation holds(The factorials are correctly calculated) not the first one.

Answer 1

This question is very confusing... You first formula is not factorial. It is simply T(n) = n + 1, for all n. Factorial of n is the product of the first n positive integers: factorial(1) = 1. factorial(n) = n * factorial(n-1). Your second formula is essentially correct.

Answer 2

Looks like T(n) is the recurrence relation of the time complexity of the recursive factorial algorithm, assuming constant time multiplication. Perhaps you misread your source?

Answer 3

we generally use recurrence relation to find the time complexity of algorithm.

---

Here, the function T(n) is not actually for calculating the value of an factorial but it is telling you about the time complexity of the factorial algorithm.

---

It means for finding a factorial of n it will take 1 more operation than factorial of n-1 (i.e. T(n)=T(n-1)+1) and so on.

---

so correct recurrence relation for a recursive factorial algorithm is T(n)=1 for n=0 T(n)=1+T(n-1) for n>0 not that you mentioned later.

---

like recurrence for tower of hanoi is T(n)=2T(n-1)+1 for n>0;

Answer 4

I assume that you have bad information. The second recurrence relation you cite is the correct one, as you have observed. The first one just generates the natural numbers.

Answer 5

Where did you find the first one ? It's completely wrong.

It's only going to add 1 each time whatever the value is .

Answer 6

What he put was not the factorial recursion, but the time complexity of it.
Assuming this is the pseudocode for such a recurrence:

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)

• I am assuming that tail-recursion elimination is not involved.

Line 2 and 3 costs a constant time, c1 and c2.
Line 4 costs a constant time as well. However, it calls factorial(n-1) which will take some time T(n-1). Also, the time it takes to multiply factorial(n-1) by n can be ignored once T(n-1) is used.
Time for the whole function is just the sum: T(n) = c1 + c2 + T(n-1).
This, in big-o notation, is reduced to T(n) = 1 + T(n-1).

This is, as Diam has pointed out, is a flat recursion, therefore its running time should be O(n). Its space complexity will be enormous though.

Answer 7

T(n) = T(n-1) + 1 is correct recurrence equation for factorial of n. This equation gives you the time to compute factorial of n NOT value of the factorial of n.

Answer 8

First you have to find a basic operation and for this example it is multiplication. Multiplication happens once in every recursion. So T(n) = T(n-1) +1 this +1 is basic operation (mutliplication for this example) T(n-1) is next recursion call.

Answer 9

TL;DR: The answer to your question actually depends on what sequence your recurrence relation is defining. That is, whether the sequence T_n in your question represents the factorial function or the running-time cost of computing the factorial function^X.

---

The factorial function

The recursive defintion of the factorial of n, f_n, is:

f_n = n • f_n-1 for n > 0 with f₀ = 1.

As you can see, the equation above is actually a recurrence relation, since it is an equation that, together with the initial term (i.e., f₀ = 1), recursively defines a sequence (i.e., the factorial function, f_n).

---

Modelling the running-time cost of computing the factorial

Now, we are going to find a model for representing the running-time cost of computing the factorial of n. Let's call T_n the running-time cost of computing f_n.

Looking at the definition above of the factorial function f_n, its running-time cost T_n will consist of the running-time cost of computing f_n-1 (i.e., this cost is T_n-1) plus the running-time cost of performing the multiplication between n and f_n-1. The multiplication is achieved in constant time. Therefore we could say that T_n = T_n-1 + 1.

However, what is the value of T₀? T₀ represents the running-time cost of computing f₀. Since the value of f₀ is initially known by definition, the running-time cost for computing f₀ is actually constant. Therefore, we could say that T₀ = 1.

Finally, what we obtain is:

T_n = T_n-1 + 1 for n > 0 with T₀ = 1.

This equation above is also a recurrence relation. However, what it defines (together with the initial term), is a sequence that models the running-time cost of computing the factorial function.

---

^X_{Taking into account how the sequence in your recurrence relation is called (i.e., Tn), I think it very likely represents the latter, i.e., the running-time cost of computing the factorial function.}