The use, here, is to recognise that repeated subtraction is O(n), but there
are division methods that are *better* than O(n). I think I'm right in
saying that normal long division is O(log n).
When talking about arithmetic, we usually talk about the sizes of the
number in digit of some base. Often base two, but commonly bignum
packages work in bases like 2**32. Which of course doesn't really
matter to the complexity, since it just turns into a constant factor.
Anyway, division by repeated subtraction is O(2**n). Division by the
schoolbook method is O(n**2). The fastest ways to divide involve an
approximation and several iteration of something like Newton-Raphson,
so are O((log n) * M), where M is the complexity of multiplication,
which can be as fast as O(n * (log n) * log(log n)), for SSA (a type
of FFT transform).
Flipping that around to multiplication for a moment, since there are
fewer special cases, shows how big-O can be helpful in picking an
algorithm.
For very small multiplications, repeated addition is the fastest
route. Just look at the code any compiler generates when multiplying
by two or three.
Up to few dozen digits, the school book method, perhaps with some
minor optimizations like delayed carry propagation is your best bet.
OTOH, it will be slower than repeated additions for very small
numbers.
Up to a few thousand digits, Karatsuba (O(n**1.6)), is a good bet,
but again, the increased overhead will make it slower than schoolbook
on shorter numbers.
Above that, the FFT based algorithms are your best bet, despite having
a very high constant factor, which makes them wholly unsuitable for
shorter numbers.
