Complexity of factorial recursive algorithm

Question

Today in class my teacher wrote on the blackboard this recursive factorial algorithm:

int factorial(int n) {
   if (n == 1) 
       return 1;
   else 
       return n * factorial(n-1);
}

She said that it has a cost of T(n-1) + 1.

Then with iteration method she said that T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, so the algorithm stops when n - j = 1, so j = n - 1.

After that, she substituted j in T(n-j) + j, and obtained T(1) + n-1.

She directly said that for that n-1 = 2^(log₂n-1), so the cost of the algorithm is exponential.

I really lost the last two steps. Can someone please explain them to me?

i would like to share an old thread which can be used. Link_TO_Thread — DEBASIS PANDA
– DEBASIS PANDA, Commented Oct 3, 2019 at 19:39
The above written function goes into an infinite loop for factorial(0). — Asis
– Asis, Commented Aug 18, 2020 at 12:32

Community · Accepted Answer · 2017-05-23 12:00:06Z

29

Let's start off with the analysis of this algorithm. We can write a recurrence relation for the total amount of work done. As a base case, you do one unit of work when the algorithm is run on an input of size 1, so

T(1) = 1

For an input of size n + 1, your algorithm does one unit of work within the function itself, then makes a call to the same function on an input of size n. Therefore

T(n + 1) = T(n) + 1

If you expand out the terms of the recurrence, you get that

T(1) = 1
T(2) = T(1) + 1 = 2
T(3) = T(2) + 1 = 3
T(4) = T(3) + 1 = 4
...
T(n) = n

So in general this algorithm will require n units of work to complete (i.e. T(n) = n).

The next thing your teacher said was that

T(n) = n = 2^{log₂ n}

This statement is true, because 2^log₂x = x for any nonzero x, since exponentiation and logarithms are inverse operations of one another.

So the question is: is this polynomial time or exponential time? I'd classify this as pseudopolynomial time. If you treat the input x as a number, then the runtime is indeed a polynomial in x. However, polynomial time is formally defined such that the runtime of the algorithm must be a polynomial with respect to the number of bits used to specify the input to the problem. Here, the number x can be specified in only Θ(log x) bits, so the runtime of 2^{log x} is technically considered exponential time. I wrote about this as length in this earlier answer, and I'd recommend looking at it for a more thorough explanation.

Hope this helps!

edited May 23, 2017 at 12:00

CommunityBot

11 silver badge

answered May 4, 2013 at 20:22

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

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

3 Comments

Nuclearman Over a year ago

Sounds like Quasi-polynomial time.

A.J.Rouvoet Over a year ago

Reviving an old thread here, but I think it might be helpful to note that the teacher is correct. Because complexity is measured over an "efficient" encoding of the input. Factorial has a single int n as input, whose efficient encoding has size log n, not n! (See also my answer here: programmers.stackexchange.com/questions/181268/…)

SSH Over a year ago

@A.J.Rouvoet sir I'm sorry for reviving an old question; but sir I m trying to get this notion efficient encoding you have used, can you briefly explain this, I'm just curious to understand

Collectives™ on Stack Overflow

Complexity of factorial recursive algorithm

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related