Global optimization (differential_evolution) in SciPy - Time & Space Complexity

Time Complexity: Global optimization (differential_evolution)

O(k * m * n)

Understanding Time Complexity

When using global optimization like differential_evolution, we want to know how the time needed grows as the problem size grows.

We ask: How does the number of calculations change when we try to find the best solution over more variables?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.optimize import differential_evolution

def objective(x):
    return sum(x**2)

bounds = [(-5, 5)] * 3
result = differential_evolution(objective, bounds)
print(result.x, result.fun)

This code tries to find the minimum of a simple function with 3 variables using differential evolution.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Evaluating the objective function many times for different candidate solutions.
• How many times: The algorithm tests many candidate points across multiple generations until it converges.

How Execution Grows With Input

As the number of variables (dimensions) increases, the number of candidate solutions needed grows, so the total evaluations grow quickly.

Input Size (n variables)	Approx. Evaluations
3	Thousands
10	Tens of thousands
50	Hundreds of thousands or more

Pattern observation: The work grows faster than just adding variables; it grows roughly exponentially because the search space gets much bigger.

Final Time Complexity

Time Complexity: O(k * m * n)

This means the time grows with the number of generations (k), the population size (m), and the number of variables (n), which all increase the work.

Common Mistake

[X] Wrong: "The time to find the best solution grows linearly with the number of variables."

[OK] Correct: Because the search space grows exponentially with variables, the algorithm needs many more evaluations, so time grows faster than linearly.

Interview Connect

Understanding how optimization time grows helps you explain trade-offs when solving real problems, showing you know how algorithms behave as problems get bigger.

Self-Check

"What if we increase the population size in differential_evolution? How would the time complexity change?"