Question on Complexity of Algorithm

values = [1, 3 ,5, 7, 11, 13]
sums = [sum(values) / i for i in range(1, N)]

Hi!

why has this algorithm a complexity of O (M*N)?
M=elements of values
I would think it has the complexity of O(1*N)

I mean, the sum() function is for every iteration the same value?
The code is from : dataquest

Thank you!

That is a very good observation.

For every iteration of the for loop, we call sum(). And sum() is a function that adds those M values. For a list, sum() will have a linear time complexity because the function has to go through all the numbers to add them up.

So, for every iteration of the for loop, you have a piece of code that has O(M) time complexity. Because, sum() is being called every time.

You can point out that since M is fixed here and just a few numbers, then it’s equivalent to O(N) (assuming N is large enough). However, it’s usually better to consider the worst-case scenario when calculating the time complexity. The worst-case scenario would be that M is sufficiently large.

Now, if we were to modify the code:

values = [1, 3 ,5, 7, 11, 13]
sum_values = sum(values)
sums = [sum_values / i for i in range(1, N)]

In the above example, sum() is being called only once, outside the list comprehension. So, inside the loop, for every iteration, we end up with just a simple division which would be O(1). In such a case, we can say complexity is O(N).

I say this is a good observation, because going through such logic is helpful if/when you want to improve/optimize your code.

2 Likes