CODEWITHSUNDEEP
pythontime-complexity
Misha
Misha

Reputation: 377

Understanding time complexity for python code

I'm completely new to time complexity problems. I'm writing Python code for a Codility exercise and the code I've written returns time out error with a time complexity of O(N*N). The expected time complexity is O(N).

Given a list of integers A, I'm trying to compute the minimum difference between the sum of A[0:i] and the sum of A[i:], for all index i in A.

Here's my solution:

def solution(A):
    # write your code in Python 2.7
    a=[]
    for i in range(1,len(A)):
        a.append(abs(sum(A[0:i])-sum(A[i:len(A)+1])))
    return min(a)

I tried to improve the code by implementing the following

import sys
def solution(A):
    # write your code in Python 2.7
    a=sys.maxint
    for i in range(1,len(A)):
        temp=abs(sum(A[0:i])-sum(A[i:len(A)+1]))
        if temp<a:
            a=temp
    return a

I still get the same complexity. I understand the abs step is taking a lot of time to compute. How do I reduce time complexity for this code? Is there an intuitive way of looking at time complexity problems?

Upvotes: 1

Views: 735

Answers (1)

janos
janos

Reputation: 124648

In each iteration of the loop, you recalculate the sum of elements up to index i, and the sum of elements after index i. This is inefficient, because you can accumulate the sum as you go.

suffix = sum(A)
prefix = 0
mindiff = suffix

for a in A:
    prefix += a
    suffix -= a
    mindiff = min(mindiff, abs(prefix - suffix))

return mindiff

There were other issues too with your code:

  • There's no need to make a list of the differences. You can track the minimum value (as I did)
  • The end index in A[i:len(A)+1] is beyond the range of A, which is confusing to read, and it suggests that you might be confused about list indexing in Python. This should have been A[i:len(A)], or even better, simply A[i:].

Is there an intuitive way of looking at time complexity problems?

Absolutely. The intuition here is that to calculate the sum of a range of values, you need to iterate over them. So that's O(N) right there. If this is within another O(N) loop, then the overall complexity becomes O(N*N). Your mistake was overlooking the cost of summing.

Upvotes: 1

Related Questions