Error function (erf) in SciPy - Time & Space Complexity

Time Complexity: Error function (erf)

O(n)

Understanding Time Complexity

We want to understand how the time to compute the error function grows as the input size changes.

This helps us know how fast the function runs when given many values.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.special import erf

x = np.linspace(-3, 3, 1000)  # 1000 points
result = erf(x)  # compute erf for each point

This code computes the error function for 1000 points evenly spaced between -3 and 3.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Computing erf for each element in the input array.
• How many times: Once per element, so 1000 times in this example.

How Execution Grows With Input

Each input value requires one calculation of erf, so the total work grows as the number of inputs grows.

Input Size (n)	Approx. Operations
10	10 calculations
100	100 calculations
1000	1000 calculations

Pattern observation: The work increases directly with the number of inputs.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute grows linearly with the number of input values.

Common Mistake

[X] Wrong: "Computing erf for many values takes the same time as for one value because it is a built-in function."

[OK] Correct: Even built-in functions must process each input separately, so more inputs mean more work and more time.

Interview Connect

Understanding how function calls scale with input size helps you explain performance clearly and shows you think about efficiency in real tasks.

Self-Check

"What if we used a vectorized erf call on a 2D array instead of a 1D array? How would the time complexity change?"