Description: This program takes 5 nodes and an interpolating value as input and display the process of arriving at the final result in a table form. The final result is displayed in cell F11
How to input values: The input data should be given in the first two rows. The interpolation value should be given in cell C3. The user should note that 'no two xi' should be the same. You will get an error in the program otherwise.
Theory from numerical analysis: Due to the uniqueness theorem of interpolation, given a set of n+1 data points (xi, yi) where no two xi are the same, there exists a unique polynomial p of degree at most n with the property p(xi) = yi for all i = 0,…,n.
The complexity of the algorithm: It is visually clear from the table in the spreadsheet program: Altogether are 1+2+3...+n steps required. That sums up to be n(n+1)/2. And each step takes 7 elementary arithmetical operations. In total, 7n(n+1)/2 elementary arithmetical operations. Hence this algorithm's complexity is O(n^2).
These details are provided for information only. No information here is legal advice and should not be used as such.