Romberg integration in SciPy - Time & Space Complexity

Time Complexity: Romberg integration

O(2^n)

Understanding Time Complexity

We want to understand how the time needed to compute Romberg integration changes as we increase the number of steps.

How does the work grow when we ask for more precise results?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.integrate import romberg

def f(x):
    return x ** 2

result = romberg(f, 0, 1, divmax=5)
print(result)

This code calculates the integral of x squared from 0 to 1 using Romberg integration with a maximum of 5 divisions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Evaluating the function f at multiple points for trapezoidal approximations.
• How many times: The number of function evaluations roughly doubles each iteration up to divmax.

How Execution Grows With Input

Each step doubles the number of points where the function is evaluated, so the work grows quickly.

Input Size (divmax)	Approx. Function Evaluations
1	2
3	8
5	32

Pattern observation: The number of evaluations roughly doubles each time divmax increases by 1.

Final Time Complexity

Time Complexity: O(2^n)

This means the work grows exponentially as we increase the number of refinement steps.

Common Mistake

[X] Wrong: "Romberg integration runs in linear time because it just adds more points each step."

[OK] Correct: Each step doubles the points, so the total work grows much faster than just adding a few points.

Interview Connect

Understanding how iterative numerical methods grow in work helps you explain efficiency clearly and shows you can think about algorithm costs beyond simple loops.

Self-Check

"What if we limited the function evaluations by reusing previous results? How would the time complexity change?"