CODEWITHSUNDEEP
pythonpython-2.7time-complexity
Elias
Elias

Reputation: 41

Quadratic timecomplexity: why is the following code calculated this way?

Could some one please explain why the following code complexity is calculated this way: 1+2+3+4+...+(n-2)+(n-1)+n = O(n^2)

def CalculateAveragesTotElementOverzicht(inputlist):
  resultlist = [0]*len(inputlist)
  for i in range(0,len(inputlist)):
      som = 0
      for j in range(0,i+1):
          som += inputlist[j]
      average = som/(i+1)
      resultlist[i] = average
  return resultlist

Upvotes: 2

Views: 61

Answers (1)

Kasravnd
Kasravnd

Reputation: 107317

It's not O(n) but O(n2). And that's because you have two loops which the outer one iterates from 0 to n and the inner one from 0 to the throwaway variables size (i) which in each iteration it will generate the following ranges:

range(0,0+1) # 1 iteration 
range(0,1+1) # 2 iteration
range(0,2+1) # 3 iteration
   ...

Therefore at the end, you'll have 1 + 2 + 3 + ... + n iteration which its complexity computes as fllows:

n * (n+1) / 2 = 1/2 n2 + 1/2n = O(n2)

Upvotes: 8

Related Questions