I'm not really good wih the Big O notation so I was wondering if any one can help me find the Big O notation of this code for each of its function when they are best , worst, and adverage case and a brief explantation of why it's that. Sorry if the code is long and thank you for takening your time to look at this code. Don't need to look at def main
class Polynomial(object):
"""self.a[0] is the constant term.
self.a[self.n] is the coefficient of the highest degree
if reverse is True assign reverse of c to self.a"""
def __init__(self, c, reverse = False):
if type(c)==type(1) or type(c)==type(1.1):
#coefficient c is only a number, constant polynomial
self.a = [c]
self.n = 0
elif type(c)==type([]):
if (not reverse):
self.a = [b for b in c]
else:
self.a = []
k = len(c) - 1
for i in range(len(c)):
self.a.append(c[k - i])
self.normalize()
else:
self.a = [0]
self.n = 0
def normalize(self):
"""delete leading zeros of a polynomial"""
k = len(self.a) - 1
while k > 0 and self.a[k] == 0:
self.a.pop()
k -= 1
self.a = self.a[0:k+1]#including 0, excluding k+1
self.n = len(self.a) - 1
def add(self, p):
aa = []
k = 0
while k < len(self.a) and k < len(p.a):
aa.append(self.a[k] + p.a[k])
k += 1
while k < len(self.a):#self.n is bigger than p.n
aa.append(self.a[k])
k += 1
while k < len(p.a):
aa.append(p.a[k])
k += 1
return Polynomial(aa)
def negative(self):
aa = [-b for b in self.a]
return Polynomial(aa)
def subtract(self, p):
return self.add(p.negative())
def derivative(self):
aa = []
for i in range(1, len(self.a)):
aa.append(i * self.a[i])
return Polynomial(aa)
def getDegree(self):
return self.n
def integral(self):
aa = []
aa.append(0)# for constant term
for i in range(len(self.a)):
aa.append(self.a[i]/(i+1.0))
return Polynomial(aa)
def multiply(self, p):
aa = [0 for i in range(self.n + p.n + 1)]
for i in range(len(self.a)):
for j in range(len(p.a)):
aa[i+j] += self.a[i] * p.a[j]
return Polynomial(aa)
def __str__(self):
if (self.n == 0):
return str(self.a[0])
s = "Degree " + str(self.n) + ":"
k = self.n
leftMost = True
for i in range(self.n + 1):
if self.a[k] == 0:
k -= 1
continue
s += " "
if ((not leftMost) and self.a[k] > 0):
s += "+ "
if self.a[k] < 0:
s += "- "
if (self.a[k] != -1) or (k == 0):
s += str(-self.a[k])
elif (self.a[k] != 1) or (k == 0):
s += str(self.a[k])
if (k >= 1):
s += "x"
if (k >= 2):
s += "^" + str(k)
k -= 1
leftMost = False
return s
def power(self, n):
tmp = Polynomial(self.a)
for i in range(n-1): tmp = self.multiply(tmp)
return tmp
#operator overloading
def __add__(self, p):
if type(p) == type(1) or type(p) == type(1.1):
return self.add(Polynomial(p))
if type(p) == type(self):
return self.add(p)
return self
def __sub__(self, p):
if type(p) == type(1) or type(p) == type(1.1):
return self.subtract(Polynomial(p))
if type(p) == type(self):
return self.subtract(p)
return self
def __mul__(self, p):
if type(p) == type(1) or type(p) == type(1.1):
return self.multiply(Polynomial(p))
if type(p) == type(self):
return self.multiply(p)
return self
def __neg__(self):
return self.negative()
def main():
p1 = Polynomial([0,5,4,3,2,1], True)
print "p1: " + str(p1)
print "p1.negative() " + str(p1.negative())
p2 = Polynomial([-2,3,4])
print "p2: " + str(p2)
print "p1+P2: " + str(p1.add(p2))
print "p1-P2: " + str(p1.subtract(p2))
print "p1*P2: " + str(p1.multiply(p2))
print "p2+25: " + str(p2+25)
p3 = Polynomial([1,1])
print "p3: " + str(p3)
print "p3*P3*p3: " + str(p3*p3*p3)
print "p3^4 " + str(p3.power(4))
if __name__ == '__main__':
main()
