title: Big-Oh : How can O(n) + O(n) + ... + O(n) be equal to O(n^2)?
body: <p>I'm having a hard time understanding the following statements from <a href="http://www.cs.berkeley.edu/~vazirani/algorithms/chap1.pdf" rel="nofollow noreferrer">Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani - page 24</a> that they represent the sum of O(n) as O(n<sup>2</sup>). But my understanding of O(n) is a linear function of n, and it can never be quadratic no matter how many times the linear functions are <strong>added</strong> (for any given n). They are giving the explanation like below for the example of 13 x 11 in binary notation.</p>
  
  <pre><code>        1 1 0 1
        x 1 0 1 1
        ----------
          1 1 0 1 (1101 times 1)
        1 1 0 1   (1101 times 1, shifted once)
      0 0 0 0     (1101 times 0, shifted twice)
  + 1 1 0 1       (1101 times 1, shifted thrice)
  ----------------
  1 0 0 0 1 1 1 1 (binary 143)
  </code></pre>
  
  <blockquote>
    <p>If x and y (1101 and 1011 here) are both n bits, then there
    are n intermediate rows, with lengths
    of up to 2n bits (taking the shifting
    into account). The total time taken to
    add up these rows, doing two numbers
    at a time, is <strong>O(n) + O(n) + ... +
    O(n), which is O(n<sup>2</sup>)</strong>, quadratic in
    the size of the inputs.</p>
  </blockquote>
  
  <p>Sorry if this is obvious, but could somebody please help me understand why this is O(n<sup>2</sup>)?</p>