The factorial of a nonnegative integer n, written as n!, is a mathematical calcu

Question

The factorial of a nonnegative integer n, written as n!, is a mathematical calculation that is the product of all positive integers less than or equal to n. The calculation of factorials is one of the example of the use of recursion. The calculation can be written as n! = n * (n-1) * (n-2) * … 1 where 1! = 1, and 0! is defined to be 1 as well. One of the tenets of modern Software Engineering is code reuse. There are many instances of functions that implement the factorial schema on the Internet. Locate a recursive instance , code it and test it. Use the factorial function to calculate the series: e = 1/0! + 1/1! + 1/2! + 1/3! + … for 50 terms. Write the same series calculation using an iterative loop of your choice. Instrument your code to measure time for the recursive and iterative loop methods to calculate the first 50 terms of the series. Present your timing results. Based on your timing results, comment on the quote: ”Would any of you very experienced programmers, if asked to code an iterative loop (like a mathematical series), think of using recursion or would that be a ‘mistake’ that a rookie programmer would leap to?”

Explanation / Answer

Analysis of Time complexity of factorial number using recursion is:

If you take multiplication as O(1), then yes, O(N) is correct. However, note that multiplying two numbers of arbitrary length x is not O(1) on finite hardware. as x tends to infinity, the time needed for multiplication grows (e.g. if you use Karatsuba multiplication, it's O(x ** 1.585)).

Recursion: Factorial calculation.

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

Consider n is 50 here ..the complexity is 2*50 = 100
complexity become 2*n

Iterative:-

int fact(int n)
{
    int i, result = 1;
    if(n==0)
    result = 1;
    else
         {
           for(1=1;i<=n;i++)
              result*=i;
         }
     return (result);
}

Consider n is 50 here ..the complexity is 50
Time complexity proportional to n

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.