Numerical differentiation in MATLAB - Time & Space Complexity

Time Complexity: Numerical differentiation

O(n)

Understanding Time Complexity

We want to understand how the time needed to calculate numerical derivatives changes as we use more data points.

How does the work grow when we increase the number of points to differentiate?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function dy = numerical_diff(y, h)
  n = length(y);
  dy = zeros(size(y));
  for i = 2:n-1
    dy(i) = (y(i+1) - y(i-1)) / (2*h);
  end
  dy(1) = (y(2) - y(1)) / h;
  dy(n) = (y(n) - y(n-1)) / h;
end
    

This code calculates the numerical derivative of a vector y using central differences for the middle points and forward/backward differences at the ends.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that computes the derivative for each middle point.
• How many times: It runs once for each element except the first and last, so about n-2 times.

How Execution Grows With Input

As the number of points n grows, the number of calculations grows roughly the same amount.

Input Size (n)	Approx. Operations
10	About 8 calculations
100	About 98 calculations
1000	About 998 calculations

Pattern observation: The work grows linearly as we add more points.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute the derivative grows in direct proportion to the number of points.

Common Mistake

[X] Wrong: "Because we do subtraction and division, the time grows faster than the number of points."

[OK] Correct: Each calculation is simple and done once per point, so the total work grows just as the number of points grows.

Interview Connect

Understanding how loops over data affect time helps you explain efficiency clearly and shows you can reason about code performance in real tasks.

Self-Check

"What if we used a nested loop to compute differences between every pair of points? How would the time complexity change?"