title: Solving Equi task in python
body: <p>From <a href="http://blog.codility.com/2011/03/solutions-for-task-equi.html" rel="nofollow">http://blog.codility.com/2011/03/solutions-for-task-equi.html</a></p>
  
  <p>The task is to solve an equilibrium problem. The equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. </p>
  
  <p>For example, in a sequence A:</p>
  
  <pre><code>A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0
  </code></pre>
  
  <p>i.e. </p>
  
  <pre><code>A = [-7, 1, 5, 2, -4, 3, 0]
  </code></pre>
  
  <p>3 is an equilibrium index, because:</p>
  
  <pre><code> A[0]+A[1]+A[2]=A[4]+A[5]+A[6]
  </code></pre>
  
  <p>6 is also an equilibrium index, because:</p>
  
  <pre><code>A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0
  </code></pre>
  
  <p>When I try to write a super pythonic answer, i.e.:</p>
  
  <pre><code>def solution(A):
      for i in range(len(A)):
          if sum(A[:i]) == sum(A[i+1:]):
              return i 
      return -1
  </code></pre>
  
  <p>I get a worst-case complexity of <code>O(N**2)</code>. <strong>Why is that so?</strong></p>
  
  <p><strong>How do I get a best case complexity of <code>O(N)</code>?</strong> </p>
  
  <p>Does this give me <code>O(N)</code>? <strong>Why is that so?</strong></p>
  
  <pre><code>def solution(A):
      total = sum(A)
      sum_left = 0
      for i in range(len(A)):
          sum_right = sum - sum_left
          if sum_left == sum_right:
              return i
      return -1
  </code></pre>