Consider the multiplication problem: $1234 \times 5432$. Using the "method taught in school", how many operations are carried out in this product?
If there are $n$ rows in the long multiplication, why are there $\leq 2n$ operations for each row? Why is the total number of operations $\leq Cn^2$ where $C$ is a constant?
I though in each row we are adding it to all the other rows. So wouldn't it be $n!$ for the first row, $(n-1)!$ for the second row etc.?
You basically create a matrix of the size O(n²), whose values you need to sum afterwards. Hence the O(n²). It's O(n) for each row because you touch each value exactly once.