CODEWITHSUNDEEP
python-2.7time-complexitycode-complexity
user3539924
user3539924

Reputation: 61

what is the complexity of my Python program? Complexity newbie

def multiplyItself():
 i=[2,3,1,4]
 j=[]
 length=len(i) # 0 1 2 3
 print 'input string',i
 for l in range(length):
  if l==0:
    j.append(mul(i[l+1::]))
  if l>0:
    print i[l+1::]
    print i[0:l]
    j.append(mul(i[l+1::])*mul(i[0:l]))
 print j


def mul(l):
 sum=1
 for i in l:
   sum=sum*i
 return sum

def main():
 print 'test multply'
 multiplyItself()


main()

Above python code works, but I am not sure of the programs complexity. Can anyone give me more insight?

Actual question is below: input [2,3,1,4] output [12,8,24,6]

Multiply all fields except it's own position.

Restrictions: 1. no use of division 2. complexity in O(n)

Upvotes: 0

Views: 102

Answers (1)

NPE
NPE

Reputation: 500207

Let's take it one step at a time:

  1. mul(l) performs an operation on every element of l. Its complexity is therefore O(len(l)).
  2. Since j.append(mul(i[l+1::])*mul(i[0:l])) operates on O(len(i)) elements, its complexity is O(len(i)).
  3. Since the j.append() is repeated len(i) times, the overall complexity is O(len(i)*len(i)) or O(n**2) (where n is len(i)).

In conclusion, you need a different algorithm.

Hint (mouseover to reveal):

Would it help if you were to multiply all the elements together?

Upvotes: 1

Related Questions