Understanding time complexity for python code

Question

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?

janos · Accepted Answer · 2017-07-22 10:27:30Z

1

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.

edited Jul 22, 2017 at 10:27

answered Jul 22, 2017 at 10:12

janos

126k31 gold badges242 silver badges253 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Misha Over a year ago

Thank you for your feedback. Any books that you would recommend to understand time complexity?

janos Over a year ago

@Misha I this one excellent, see the PDF link near the top of the page. codility.com/programmers/lessons/3-time_complexity I also recommend to complete the exercises on this page. In fact all the lessons here are brilliant, and all aspiring programmers should go through them.

Collectives™ on Stack Overflow

Understanding time complexity for python code

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related