Reference request: "Schoolbook long multiplication has complextity $O(n^2)$" On Wikipedia (here), it says that schoolbook long multiplication of an $n$-digit number has complexity $O(n^2)$. Can anyone help to provide a reference for this claim?
Additionally, is this claim dependent on the base in which the number $n$ is expressed, or is it the same for all bases?
 A: If you want a reference, it is covered at the start of the first chapter of Algorithms by Dasgupta, Papadimitriou and Vazirani, but it should be clear that it is true. (I vaguely recall another textbook that also starts with a treatment of arithmetic of natural numbers, but I can't seem to find it, and it's possible that I'm thinking of the book I mentioned above.) 
If $a$ and $b$ are $n$-digit numbers, then when we multiply $a$ and $b$ using the school-book method, we multiply each digit of $b$ with each digit of $a$, giving us $n^2$ single-digit multiplications. We then perform $(n-1)$ additions of numbers each with at most $2n$ digits. Since each addition is $O(2n) = O(n)$, the addition part of the process is also $O(n^2)$.
The claim is true regardless of the base that the numbers are written in. Note that $n$ represents the number of digits of the number in the base in which they are written, but actually the claim is true even if $n$ is the number of base-10 digits, and the calculation is performed in some other base.
To see this, note that the number of base-10 digits of a natural number $m$ is
$$
  \left\lfloor \log_{10} (m) \right\rfloor + 1
$$
while the number of base $b$ digits of $m$ is
$$
  \left\lfloor \log_b (m) \right\rfloor + 1.
$$
Since
$$
  \log_b (m) = \frac{\log_{10} (m)}{\log_{10} (b)},
$$
we see that the number of base-$b$ digits of $m$ is at most a constant factor of the number of base-10 digits.
