Big-Oh : How can O(n) + O(n) + ... + O(n) be equal to O(n^2)?

Question

I'm having a hard time understanding the following statements from Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani - page 24 that they represent the sum of O(n) as O(n²). 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 added (for any given n). They are giving the explanation like below for the example of 13 x 11 in binary notation.

        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)

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 O(n) + O(n) + ... + O(n), which is O(n²), quadratic in the size of the inputs.

Sorry if this is obvious, but could somebody please help me understand why this is O(n²)?

Answer 1

If there are n operations that have a complexity of O(n), then the total complexity is n·O(n) which is O(n²).