# Reduce one for loop to decrease time complexity

I'm using NumPy to find out langrage polynomial interpolation. I'm using 2 for loop to find out langrage polynomial, but I want to reduce 2nd for loop so that my code time complexity can be less. Can you guys please suggest me how I can cut a for loop to increase my time complexity.

import numpy as np
import matplotlib.pyplot as plt
class LagrangePolynomial:
def __init__(self, data_x, data_y):

assert type(data_x) == np.ndarray, "data_x is not numpy array"
assert type(data_y) == np.ndarray, "data_y is not numpy array"
assert len(data_x) == len(data_y), "length of data_x and data_y must be equal"

self.x = data_x
self.y = data_y

self.degree = len(data_x) - 1

def __str__(self):
strL = f"LagrangePolynomial of order {self.degree}\n"
strL += "p(x) = "
count=0
for i in self.y:
if i == 0:
continue
elif i >= 0:
strL += f"+ {i}*l_{count + 1}(x) "
else:
strL += f"- {-i}*l_{count + 1}(x) "
count+=1
return strL
def __call__(self,x):
y_interp = np.zeros(len(x))
for i in range(len(x)):
#remove this for loop.
for j in range(self.degree + 1):
upper=np.prod(np.delete(self.x - x[i],j))
lower=np.prod(np.delete(self.x[j] - self.x, j))
y_interp[i] +=(upper/lower)*self.y[j]
return y_interp
data_x = np.array([-3.,-2.,-1.,0.,1.,3.,4.])
data_y = np.array([-60.,-80.,6.,1.,45.,30.,16.])

p = LagrangePolynomial(data_x, data_y)

#generating 100 points from -3 to 4 in order to create a smooth line
x = np.linspace(-3, 4, 100)
print(p)
y_interp = p(x)
plt.plot(x, y_interp, 'g--')
plt.plot(data_x, data_y, 'ro')
plt.legend(['interpolated', 'node points'], loc = 'lower right')
plt.xlabel('x')
plt.ylabel('y')
plt.title('Lagrange Polynomial')

plt.show()


The second loop can be eliminated by creating a 2D array by tiling the self.x array with the np.tile method. The removal of elements in de 1D array with np.delete can than be replaced with a boolean mask (unfortunately this results in a 1D array which needs to be reshaped).

The calculation of the 2D array can be done outside the first loop, as can be the calculation of lower as they do not depend on x.

See my rewrite of the __call__ method:

def __call__(self,x):

y_interp = np.zeros(len(x))

n = self.degree + 1

tiled = np.tile(self.x, (n,1))