Factorial in Python with O(n) Time Complexity

Given a non-negative integer n return the factorial of n, also denoted as n!

n! = 1 * 2 * 3 * ... * (n - 1) * n

Example:

Input: n = 5
Output: 120
Explanation: 5! = 1 * 2 * 3 * 4 * 5 = 120

Note:

Your algorithm should run in O(n) time and use O(1) space.

Understanding the Problem

The core challenge of this problem is to compute the factorial of a given non-negative integer n. The factorial of a number is the product of all positive integers less than or equal to that number. Factorials are commonly used in permutations, combinations, and other mathematical computations.

Potential pitfalls include handling the edge case where n is 0, as 0! is defined to be 1.

Approach

To solve this problem, we can use an iterative approach. The naive solution involves using a loop to multiply the numbers from 1 to n. This approach is straightforward and efficient for this problem.

We initialize a variable fact to 1 and then iterate from 1 to n, multiplying fact by the current number in each iteration.

Algorithm

Initialize fact to 1.
Iterate from 1 to n.
In each iteration, multiply fact by the current number.
Return fact after the loop ends.

Code Implementation

def factorial(n):
    # Initialize the result to 1
    fact = 1
    
    # Iterate from 1 to n
    for i in range(1, n + 1):
        # Multiply fact by the current number
        fact *= i
    
    # Return the computed factorial
    return fact

# Example usage
n = 5
print(factorial(n))  # Output: 120

Complexity Analysis

The time complexity of this approach is O(n) because we have a single loop that iterates n times. The space complexity is O(1) because we are using a constant amount of extra space regardless of the input size.

Edge Cases

One important edge case is when n is 0. By definition, 0! is 1. Our algorithm handles this case correctly because the loop does not execute, and fact remains 1.

# Edge case
print(factorial(0))  # Output: 1

Testing

To test the solution comprehensively, we should include a variety of test cases:

Simple cases: n = 1, 2, 3
Edge case: n = 0
Large values: n = 10, 20

# Simple cases
print(factorial(1))  # Output: 1
print(factorial(2))  # Output: 2
print(factorial(3))  # Output: 6

# Edge case
print(factorial(0))  # Output: 1

# Large values
print(factorial(10))  # Output: 3628800
print(factorial(20))  # Output: 2432902008176640000

Thinking and Problem-Solving Tips

When approaching problems like this, it's important to:

Understand the mathematical definition and properties of the problem.
Start with a simple, naive solution and then optimize if necessary.
Consider edge cases and test your solution thoroughly.

Conclusion

In this blog post, we discussed how to compute the factorial of a non-negative integer using an iterative approach in Python. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.