NC task

 Task:

1. Using Newton’s Backward Interpolation Formula, estimate the execution time for N = 2250.

2. Interpret the result: What does the estimated time suggest about the algorithm's performance?

Solution:

The estimated time of 51.85 ms suggests that the algorithm’s performance deteriorates as input size increases, indicating non-linear time complexity (e.g., $O(N^2)$). This may limit its scalability and efficiency for handling larger datasets.

3. Write a MATLAB or Python script that performs the above calculations and displays the results.

Solution:

import math

N = [500, 1000, 1500, 2000, 2500]

execution_times = [8.12, 16.24, 27.36, 42.48, 61.60]

n = len(execution_times)

backward_diff = [execution_times.copy()]

for i in range(1, n):

    diff = [round(backward_diff[i - 1][j + 1] - backward_diff[i - 1][j], 4) for j in range(n - i)]

    backward_diff.append(diff)

print("Backward Differences Table:")

for i in range(n):

    print(f"∇^{i} y:", backward_diff[i])

x = 2250

x_0 = 2000 

h = 500 

p = (x - x_0) / h  

f_x = execution_times[3]  # f(2000) = 42.48

factorial = lambda k: math.factorial(k)  

f_x += p * backward_diff[1][2]

f_x += (p * (p + 1) / 2) * backward_diff[2][1]

f_x += (p * (p + 1) * (p + 2) / 6) * backward_diff[3][0]

f_x += (p * (p + 1) * (p + 2) * (p + 3) / 24) * backward_diff[4][0]

print(f"\nEstimated execution time for N = {x}: {f_x:.4f} milliseconds")