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?"

Practice

1. Which method in numerical differentiation uses points on both sides of the target point to estimate the derivative?

easy

A. Forward difference method

B. Euler's method

C. Backward difference method

D. Central difference method

Solution

1. Step 1: Understand difference methods

   Forward difference uses the point and the next point; backward difference uses the point and the previous point.

2. Step 2: Identify method using both sides

   Central difference uses points before and after the target point for better accuracy.

3. Final Answer:

   Central difference method -> Option D

4. Quick Check:

   Both sides points = Central difference [OK]

Hint: Central difference uses points on both sides [OK]

Common Mistakes:

• Confusing forward with central difference
• Thinking Euler's method is for differentiation
• Assuming backward difference uses both sides

2. Which of the following MATLAB code snippets correctly computes the forward difference approximation of the derivative of function f at point x with step size h?

easy

A. df = (f(x+h) - f(x)) / h;

B. df = (f(x) - f(x-h)) / h;

C. df = (f(x+h) - f(x-h)) / (2*h);

D. df = (f(x) + f(x+h)) / h;

Solution

1. Step 1: Recall forward difference formula

   Forward difference formula is (f(x+h) - f(x)) / h.

2. Step 2: Match code to formula

   df = (f(x+h) - f(x)) / h; matches this formula exactly.

3. Final Answer:

   df = (f(x+h) - f(x)) / h; -> Option A

4. Quick Check:

   Forward difference = (f(x+h)-f(x))/h [OK]

Hint: Forward difference subtracts current from next point [OK]

Common Mistakes:

• Using backward difference formula instead
• Dividing by 2*h instead of h
• Adding function values instead of subtracting

3. Consider the MATLAB code:

f = @(x) x^2;
x = 2;
h = 0.01;
df = (f(x+h) - f(x-h)) / (2*h);

What is the value of df approximately?

medium

A. 5.00

B. 2.00

C. 4.00

D. 3.99

Solution

1. Step 1: Calculate f(x+h) and f(x-h)

   f(2+0.01) = (2.01)^2 = 4.0401; f(2-0.01) = (1.99)^2 = 3.9601.

2. Step 2: Compute central difference

   df = (4.0401 - 3.9601) / (2*0.01) = 0.08 / 0.02 = 4.00.

3. Step 3: MATLAB precision

   In MATLAB, df is computed and displayed as 4.0000.

4. Final Answer:

   4.00 -> Option C

5. Quick Check:

   Central difference ≈ 4 [OK]

Hint: Central difference approximates slope near x [OK]

Common Mistakes:

• Using forward difference formula instead
• Forgetting to divide by 2*h
• Incorrect function evaluation

4. The following MATLAB code attempts to compute the derivative using forward difference but gives incorrect results:

f = @(x) sin(x);
x = pi/4;
h = 0.001;
df = (f(x) - f(x+h)) / h;

What is the error in this code?

medium

A. Step size h is too large

B. The subtraction order is reversed; should be f(x+h) - f(x)

C. Function handle syntax is incorrect

D. Variable x should be a vector

Solution

1. Step 1: Recall forward difference formula

   Forward difference is (f(x+h) - f(x)) / h, not (f(x) - f(x+h)) / h.

2. Step 2: Identify error in code

   The code subtracts f(x+h) from f(x), reversing the order and causing incorrect sign.

3. Final Answer:

   The subtraction order is reversed; should be f(x+h) - f(x) -> Option B

4. Quick Check:

   Forward difference = (f(x+h)-f(x))/h [OK]

Hint: Forward difference subtracts future minus current value [OK]

Common Mistakes:

• Reversing subtraction order
• Using too large step size without reason
• Misunderstanding function handle syntax

5. You want to estimate the derivative of f(x) = exp(-x^2) at x = 1 using central difference in MATLAB. Which code snippet correctly implements this with step size h = 0.0001?

hard

A. f = @(x) exp(-x^2);
x = 1;
h = 0.0001;
df = (f(x+h) - f(x-h)) / (2*h);

B. f = @(x) exp(-x^2);
x = 1;
h = 0.0001;
df = (f(x) - f(x-h)) / h;

C. f = @(x) exp(-x^2);
x = 1;
h = 0.0001;
df = (f(x+h) + f(x-h)) / (2*h);

D. f = @(x) exp(-x^2);
x = 1;
h = 0.0001;
df = (f(x+h) - f(x)) / h;

Solution

1. Step 1: Recall central difference formula

   Central difference formula is (f(x+h) - f(x-h)) / (2*h) for better accuracy.

2. Step 2: Match code to formula

   f = @(x) exp(-x^2); x = 1; h = 0.0001; df = (f(x+h) - f(x-h)) / (2*h); matches the central difference formula exactly with correct function and step size.

3. Final Answer:

   f = @(x) exp(-x^2); x = 1; h = 0.0001; df = (f(x+h) - f(x-h)) / (2*h); -> Option A

4. Quick Check:

   Central difference = (f(x+h)-f(x-h))/(2*h) [OK]

Hint: Central difference uses symmetric points around x [OK]

Common Mistakes:

• Using forward or backward difference instead
• Adding function values instead of subtracting
• Dividing by h instead of 2*h