Factorial and gamma functions in SciPy - Time & Space Complexity

Time Complexity: Factorial and gamma functions

O(1)

Understanding Time Complexity

We want to understand how the time to compute factorial and gamma functions grows as the input number gets bigger.

How does the calculation time change when the input increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.special import factorial, gamma

n = 1000
fact_result = factorial(n, exact=False)
gamma_result = gamma(n)

This code calculates the factorial and gamma values for a number n using scipy functions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Applying approximation formulas like Lanczos or Stirling series (scipy's factorial(exact=False) uses gamma).
• How many times: Fixed number of arithmetic operations, independent of n.

How Execution Grows With Input

As n grows, the calculation uses the same fixed number of operations via approximation methods, so execution time remains roughly constant.

Input Size (n)	Approx. Operations
10	Fixed ~20 operations
100	Fixed ~20 operations
1000	Fixed ~20 operations

Pattern observation: The number of operations is constant, independent of n.

Final Time Complexity

Time Complexity: O(1)

This means the time to compute is roughly constant regardless of the input size.

Common Mistake

[X] Wrong: "Factorial requires O(n) multiplications from 1 to n."

[OK] Correct: Scipy uses constant-time approximations (e.g., Lanczos for gamma), not a naive loop.

Interview Connect

Understanding how calculation time grows helps you explain efficiency clearly and shows you can think about performance in real tasks.

Self-Check

"What if we used the exact=True option in factorial? How would the time complexity change?"