title: Complexity of array sum with divide and conquer
body: <p>Let the following algorithm be:</p>
  
  <pre><code>sum(v, i, j) {
      if i == j
          return v[i]
      else {
          k = (i + j) / 2
          return sum(v, i, k) + sum(v, k+1, j)
      }
  }
  </code></pre>
  
  <p>The time complexity of this algorithm is <code>O(n)</code>, but how can I prove (in natural language) its complexity? The problem always gets divided in two new problems so that would be <code>O(log n)</code>, but where does the rest of the complexity come from?</p>
  
  <p>Applying master theorem yields the expected result, <code>O(n)</code>.</p>
  
  <p>Thanks.  </p>