CODEWITHSUNDEEP
pythoncomplexity-theory
Romy
Romy

Reputation: 11

Reasoning behind Quadratic Complexity in this particular code

I am asking in reference to this code: 

array = [-37,-36,-19,-99,29,20,3,-7,-64,84,36,62,26,-76,55,-24,84,49,-65,41]
print sum(i for i in array if array.index(i) % 2 == 0)*array[-1] if array != [] else 0

You could see it here: Python code for sum with condition
Is this Quadratic because of a for loop followed by an if statement, inside the brackets?

Is this code, proposed by one more person on the same page - array[-1] * sum(array[::2]) free of Quadratic behaviour?
I think, it's again a Quadratic one, as it has to do a traversal and that too an alternate one.

Thanks in advance.

Upvotes: 0

Views: 71

Answers (2)

skyking
skyking

Reputation: 14368

Yes, it's the array.index that makes it quadratic.

Let's first cut all irrelevant stuff away. The conditionals are for the complexity reasoning irrelevant (we will have array != [] and that check takes O(1) time). The same goes with the multiplication with array[-1]. So you're left with:

sum(i for i in array if array.index(i) % 2 == 0)

Now the inner is a generator and it would expand to an annonymous function looping through array and yielding a bunch of values, at most one per iteration. The sum function receives these values and adds them up.

The confusing thing maybe how a generator actually works. It actually works by running the generator intermixed with code from the consumer. This results in the complexity is the sum of the complexity of the generator and the consumer (ie sum). Now sum has linear complexity (it should have, it would if I wrote it).

So for the generator, it loops through the array, but for each element in the array it calls array.index which is of O(N) complexity.

To fix this you might use enumerate to avoid having to call array.index(i), it may or may not be what you want to do since array.index(i) returns the first index for which the element is i which might not be the index where you actually found i:

sum(i for idx, i in enumerate(array) if idx % 2 == 0)

To see the difference consider the list array = [0, 1, 2, 2], the first solution should sum up this to 4 since array.index(2) == 2 so it would also add the second 2. The later solution however will add up to 2 since enumerate will enumerate the elements in array, yielding pairs (0,0), (1,1), (2,2), (3,2) - where the first component is the actual index while the second is the actual element. Here the second 2 is omitted because it's actually got from index 3.

Upvotes: 1

mutantacule
mutantacule

Reputation: 7073

The first solution is indeed quadratic: when you call array.index you basically iterates each time on array again, so it behaves like an embedded loop.

The second solution traverses the list only one time, skipping each odd indexes.

Upvotes: 0

Related Questions