Finding the time complexity of the following program that uses recursion

algorithm-analysisbig ocomplexityrecursion

I need to find the time complexity in terms of Big Oh notation for the following program which computes the factorial of a given number: The program goes like this:

public int fact(int n){

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

I know that the above program uses recursion but how to derive the time complexity for the above program?

Best Answer

This solution can be easily transformed into much simplier:

int res = 1;
for(int i = 1; i <= n; ++i) {
    res *= i;
}

Considering that multiplication is O(1) (if using Karatsuba multiplication, it's O(m^1.585), where m is the length of a number) the result is O(n) for this function.

Related Topic