Take the 2-minute tour ×


public int fact(int n){

  if (n <=1)
    return 1;
  return n * fact (n-1);


share|improve this question
Is this homework? –  MichaelT Jan 2 '13 at 17:39
No. I am a beginner to learning Algorithm analysis. –  Pradeep Jan 2 '13 at 17:44

4 Answers 4

This solution can be easily transformed into much simplier:

int res = 1;
    res *= i;


share|improve this answer
I understand the above program and the derivation for the above modified version. I wanted to know how to derive the time complexity with regards to the implementation using recursion. –  Pradeep Jan 2 '13 at 17:44
@Pradeep: This version is identical to the recursion version. So, the complexity is the same. –  m0nhawk Jan 2 '13 at 17:47



We have to define a recursive time equation:


If you resolve this equation, you will get:


This is basically:


where k is n-1 and therefore:



share|improve this answer

I'm sorry for reviving an old question, but I think a mistake might be made here that is repeated over and over.

As far as I know, computational complexity is defined over the size of an efficient encoding of the input (n).

Given an input number m for for factorial, it is true that the algorithm requires m multiplications. But this is not of linear order (i.e. the same order as the size of the encoded input), because an efficient encoding of a number m is of size n := log m

This means that the time complexity indeed IS exponential (m = 2^n multiplications) in the size of (an efficient encoding of) the input!

m multiplications are only linear in the input if you choose a unary encoding of the input, which is not an "efficient" choice.

share|improve this answer

Recurrence equation:

           | e                if n = 1
T(n) =     |



Method for Chip & Conquer



        c > 0 (the chipping factor)

        of other subproblems)

    then T(n) can be asymptotically bounded as follows:


share|improve this answer

Your Answer


