finding the time complexity of the following program

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? Please explain.

-
No. I am a beginner to learning Algorithm analysis. –  Pradeep Jan 2 '13 at 17:44
When reading the answers, keep in mind that big-O notation expresses the number of times of an algorithm iterates over the data it processes, not the execution time for the operations that take place during each iteration. Factorial, which iterates once over the set [1..n] is O(n) whether the multiplication takes a microsecond or a week. –  Blrfl Jan 2 '13 at 22:28

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.

-
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
Actually, the space complexity is different (unless you assume a very specific optimization which is not done in many major languages [implementations]). And to piggyback on this transformation when proving the space complexity, you'd have to prove equivalence (which is easy, yes, but it's not the point of the exercise). –  delnan Jan 2 '13 at 19:28

Okay, let's assume multiplication takes time as m0nhawk suggests.

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:

But if you assume that multiplication takes constant time, O(n) is the correct runtime approximation.

-
And n is from n! and m is the number of digits in n? And I'm kinda confused with the O(m^1.585), m - that's time and space complexity? –  m0nhawk Jan 2 '13 at 19:33
@m0nhawk I don't get your point. According to your answer and the Wikipedia article: Multiplying two numbers [where the greater one is] n with m digits takes O(m^1.585) or O(log_10(n)^1.585) runtime. This is not about space complexity. –  meisterluk Jan 2 '13 at 19:44
@meisterluk: I mean, what you mean by comma in the first big equation started by O(m^1.585), m. log10(n) is a good approximation of the number of digits. –  m0nhawk Jan 2 '13 at 19:52
@m0nhawk The comma only separate formulas from each other. More self-explanatory characters to separate formulas are probably ";" or newlines. I introduced spaces for clarification now. –  meisterluk Jan 2 '13 at 20:05
For those wondering about the differing costs of multiplication: The algorithm for multiplying two numbers is not O(1). There is no O(1) algorithm for multiplying two numbers. Even reading a number from memory cannot be done in constant time. However, if you are using a single assembly-level multiply instruction, you can usually treat multiplication as O(1). In reality, this is a cheat, as it bounds n to the size of the CPU register. By definition of Big-O, any halting function takes O(1) if you bound the inputs. Still, calling multiplication O(1) is a useful fiction. –  Brian Jan 2 '13 at 21:14

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.

-

Recurrence equation:

           | e                if n = 1
T(n) =     |
| T(n - 1) + d     if n > 1

f(n) = d so is a 0-degree polynomial, n^0

T(n) ∈ Θ(n^0+1) = Θ(n)


Method for Chip & Conquer

The problem of size n is chipped down into one subproblem of size n-c.

T(n) = T(n - c) + f(n)

If
c > 0 (the chipping factor)

f(n) - nonrecursive cost (to create subproblem and/or combine with solutions
of other subproblems)

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

If f(n) is a polynomial nα, then T(n) ∈ Θ(n^α+1)

If f(n) is lg n, then T(n) ∈ Θ(n lg n)

-