Newton Divided Differences Coefficient

Problem

Compute the divided difference f[x0, x1, ..., xk] of order k for the points [x_i, y_i].

Build the table in place: order 0 holds the y values, and each higher order entry is (v[i+1] - v[i]) / (x[i+order] - x[i]). Return the single top entry after k passes. Assume the x values are distinct.

Hint

The order-k divided difference uses exactly the first k+1 points.

Test cases

case 1

in: [[[0,1],[1,2],[2,5]],0]

expected: 1

case 2

in: [[[0,1],[1,2],[2,5]],2]

expected: 1

case 3

in: [[[0,0],[2,1],[4,8]],2]

expected: 0.75

case 4

in: [[[0,0],[1,1],[2,8],[3,27]],3]

expected: 1

case 5

in: [[[1,2],[3,4],[7,20]],2]

expected: 0.5

Starter codePython

def divided_difference(points, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor