Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

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
    
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

4 Answers 4

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.

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
2  
@Pradeep: This version is identical to the recursion version. So, the complexity is the same. –  m0nhawk Jan 2 '13 at 17:47
2  
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 O(n^1.585) time as m0nhawk suggests.

O_m_1.585_m_log_10_n_log_10_n_1.585.gif

We have to define a recursive time equation:

Recursive time equation: T(n) = \left{\begin{array}{ll} \mathcal{O}(1) & n = 1 \ \mathcal{O}({\log_{10}(n)}^{1.585}) + T(n-1) & \text{else} \end{array} \right.

If you resolve this equation, you will get:

Sum

This is basically:

k\cdot\mathcal{O}\left({\log_{10}(n)}^{1.585}\right) + \mathcal{O}(1)

where k is n-1 and therefore:

\mathcal{O}\left(n\cdot{\log(n)}^{1.585}\right)

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

share|improve this answer
    
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
1  
@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.

share|improve this answer

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)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.