title: time complexity of summing algorithms
body: <p>I've had a look through previous posts and I'm still struggling to find the T(n) and big O of these two recursive algorithms, each one takes a sequence of numbers as its argument and sums all numbers in the list (except for last item) then adds the sum to the last item. could anyone please shed some light.</p>
  
  <pre><code>def sum(numberSequence):
      assert (len(numberSequence) &gt; 0)
      if (len(numberSequence) == 1):
          return numberSequence[0]
      else:
          return sum(numberSequence[-1]) + numberSequence[:-1]
  </code></pre>
  
  <p>(I believe the bigO is <code>O(n)</code> as in worst case, the function is called n-1 times, but not sure what happens when it is only summing part of the list. I have <code>T(n) = n x n-1 + n = O(n)</code> it just doesn't seem right).</p>
  
  <pre><code>def binarySum(numberSequence):
      assert (len(numberSequence) &gt; 0)
      breakPoint = int(len(numberSequence)/2)
      if (len(numberSequence) == 1):
          return numberSequence[0]
      else:
          return binarySum(numberSequence[:breakPoint]) + binarySum(numberSequence[breakPoint:])
  </code></pre>
  
  <p>I'm more lost on this one, I think the big O is <code>O(log2 n)</code> as it is binary search but the whole list isn't being divided in half, only most of the list.</p>
  
  <p>Any help would be appreciated.</p>