ODE solvers (ode45) in MATLAB - Time & Space Complexity

Time Complexity: ODE solvers (ode45)

O(n)

Understanding Time Complexity

When solving ordinary differential equations (ODEs) with ode45, it is important to understand how the time to solve grows as the problem size or time span increases.

We want to know how the number of calculations changes when we ask ode45 to solve over longer times or with more complex equations.

Scenario Under Consideration

Analyze the time complexity of the following ode45 usage.

    function dydt = simpleODE(t, y)
        dydt = -2 * y + sin(t);
    end

    tspan = [0 10];
    y0 = 1;
    [t, y] = ode45(@simpleODE, tspan, y0);
    

This code solves a simple ODE from time 0 to 10 starting at y=1 using ode45.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: ode45 repeatedly evaluates the ODE function at many time points.
• How many times: The number of function evaluations depends on the solver's step size and error control, which adapts to the problem.

How Execution Grows With Input

As the time span or complexity of the ODE increases, ode45 takes more steps, so the number of operations grows roughly in proportion to the length of the time interval.

Input Size (time span length)	Approx. Operations (function calls)
10	~100 to 200
100	~1000 to 2000
1000	~10,000 to 20,000

Pattern observation: Doubling the time span roughly doubles the number of steps and function evaluations.

Final Time Complexity

Time Complexity: O(n)

This means the time to solve grows roughly linearly with the length of the time interval or the number of steps needed.

Common Mistake

[X] Wrong: "ode45 always takes the same number of steps regardless of the time span or equation complexity."

[OK] Correct: ode45 adapts its step size based on the problem and interval length, so more time or harder equations mean more steps and more work.

Interview Connect

Understanding how numerical solvers like ode45 scale helps you explain performance in simulations and scientific computing tasks, showing you grasp practical algorithm behavior.

Self-Check

"What if we changed the solver from ode45 to ode15s for stiff problems? How would the time complexity change?"