Factorial Program in Java

The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. The factorial is normally used in Combinations and Permutations (mathematics). Factorial of n is denoted by n!.

The formula for calculating the factorial of a number n is:

Edge Cases

0!=1

The Factorial is undefined for a negative integer

Example

Here, 4! is pronounced as "4 factorial." It is also called "4 bang" or "4 shriek."

Factorial Program in Java

There are many ways to write a factorial program in Java.

• Using a for Loop
• Using a while Loop
• Using a do-while Loop
• Using Recursion
• Using Dynamic Programming

Using a for Loop

Let's see the factorial Program using a loop in Java.

Output:

Factorial of 5 is: 120

Time Complexity: O(n)

The iterative approach implements a single loop that starts from 1 and ends with n. Each iteration takes a constant amount of time (to multiply).

Space Complexity: O(1)

The iterative approach allocates only a fixed additional space, regardless of the size of the input. It does not depend on the last number in a series (n).

Using a while Loop

Output:

Factorial of 6 is: 720

Time Complexity: The while loop iterates from 1 to n, performing one multiplication per iteration. So, for input n, the loop runs n times. Therefore, the time complexity is O(n).

Space Complexity: No recursion or dynamic memory allocation is used, so the space complexity is O(1).

Using a do-while Loop

Output:

Factorial of 3 is: 6

Time Complexity: The while loop iterates from 1 to n, performing one multiplication per iteration. So, for input n, the loop runs n times. Therefore, the time complexity is O(n).

Space Complexity: No recursion or dynamic memory allocation is used, so the space complexity is O(1).

Using Recursion

Let's see the factorial program in Java using recursion.

Output:

Factorial of 4 is: 24

Time Complexity: O(n)

This, too, has a time complexity of O(n), with the worst-case scenario involving n recursive calls in a constant amount of time.

Space Complexity: O(n)

The space complexity of the recursive operations is O(n), as for every function call, memory is allocated for the call stack. In the worst case, the size of the recursion tree is n, which means that the call stack uses O(n) space.

Using Dynamic Programming

1. Tabulation (Bottom-up) Approach

The tabulation approach involves filling up a table (usually an array) iteratively to store the results of subproblems, starting from the smallest subproblems and building up towards the final solution.

Let's see the factorial program in Java using Tabulation.

Output:

Factorial of 7 is: 5040

Time Complexity: O(n)

The tabulation approach cycles through numbers 1 to n just once to compute their factorials. Consequently, the time complexity is O(n), which is a linear relationship with the input size(n).

Space Complexity: O(n)

The space complexity is also O(n), as the size of the array is n+1 for the storage of the factorial values.

Memorization (Top-down DP) Approach

Memorization approach involves storing the results of already computed subproblems to avoid redundant computations during recursion.

Let's see the factorial program in Java using Memorization.

Output:

Factorial of 8 is: 40320

Time Complexity: O(n)

However, though it seems the time complexity of O(n^2) comes from the recursive calls, memoization makes sure that every value gets computed only once. In other words, the complexity of the algorithm is linear in time.

Space Complexity: O(n)

The time complexity is O(n) since it is a recursive algorithm that uses the call stack. More importantly, the value of the memoization cache (HashMap) is O(n) in space complexity since n entries with each constant size can be stored.