Double integral (dblquad) in SciPy - Time & Space Complexity

Time Complexity: Double integral (dblquad)

O(n^2)

Understanding Time Complexity

When we calculate a double integral using scipy's dblquad, we want to know how long it takes as the problem size grows.

We ask: How does the work increase when we ask for more accuracy or a bigger area?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.integrate import dblquad

def f(y, x):
    return x * y

result, error = dblquad(f, 0, 1, lambda x: 0, lambda x: 1)
    

This code calculates the double integral of the function f(y, x) = x * y over the square from 0 to 1 in both x and y directions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Evaluating the function f many times at different points.
• How many times: The function is called repeatedly for each sample point in the x and y directions.

How Execution Grows With Input

As we ask for more accuracy, dblquad uses more sample points in both directions.

Input Size (n)	Approx. Operations
10	About 100 function calls
100	About 10,000 function calls
1000	About 1,000,000 function calls

Pattern observation: Doubling the number of points in each direction squares the total work.

Final Time Complexity

Time Complexity: O(n^2)

This means the work grows roughly with the square of the number of points used in each direction.

Common Mistake

[X] Wrong: "The time grows linearly with the number of points because we just add more samples."

[OK] Correct: Because dblquad samples points in two directions, increasing points in both directions multiplies the total number of function calls.

Interview Connect

Understanding how nested sampling affects time helps you explain performance in numerical methods clearly and confidently.

Self-Check

"What if we changed dblquad to integrate only in one direction? How would the time complexity change?"