I'll add my voice to the chorus: you fundamentally misunderstand
what it means.
To say that an algorithm is O(n^2) means that as n approaches
infinity, the complexity of the algorithm approaches n^2 (perhaps
multiplied by some constant).
This is true -- or more precisely, g(n) = O(f(n)) means g(n) is
bounded above by f(n). That is, there is some constant c and value
x-sub-0 such that for all x > x-sub-0, g(x) <= c f(x). (There are
also Omega and Theta notations for bounded below, and bounded on
both sides.)
But:
It is meaningless to assert "Operation X is O(1) on two 64-bit
numbers".
This is *not* true. If k is any constant, O(k) and O(1) mean
the same thing, since the constant can be "moved out": if k is
a constant, then g(k) = k g(1), so we can replace c f(x) with
(k*c) f(x) above.
As an aside, if some algorithm is O(1), it is also automatically
O(n) and O(n^2) and O(exp(n)), since big-O notation merely gives
you an upper bound. (One should use Theta(n) instead of O(n) if
one wishes to disallow this.)
Big-O notation is for describing how the metrics of
an algorithm grow as the size of the parameters grows. It
cannot be used to assess one specific instance.
Again, it *can*. It is just not particularly *useful* to do so.
But we do it all the time.
To say that multiplication is O(n^2) is to say that a 128-bit
multiplication takes roughly 4 times as many bit operations
as a 64-bit multiplication.
(Again, this is only strictly true if you say it is Theta(n^2).)
In any case, the real problems here (there are two) are:
(a) In C, we do not compute a 2n-bit product when multiplying
two n-bit numbers. Instead, we prefer to get the wrong answer
as fast as possible, so we retain only the lower n bits of
the result (with -- for signed integers -- undefined behavior
if the result does not fit in those n bits, although typically
overflow is ignored; for unsigned integers, overflow is always
deliberately ignored.)
(b) Again, in order to get the wrong answer as fast as possible,
we set "n" to a constant. And when n is a constant, O(n)
*is* O(1) (because O(32) is just O(1), as is O(64), or even
O(1048976)).
To avoid both of those problems, we have to write functions to
operate on "bignums", and replace the simple:
result = n1 * n2;
syntax with, e.g.:
struct bignum *n1, *n2, *result;
...
result = bignum_multiply(n1, n2);
or similar. Now we can calculate the correct answer slowly, and
use an algorithm in which the number of bits is not a constant,
and therefore get multiplication that is indeed O(mn) (where m
and n are the number of bits needed for n1 and n2 respectively).
If C were C++, we could use operator overloading to make:
result = n1 * n2;
into syntactic sugar for a call to bignum_multiply(), and therefore
compute the right answer slowly, with an O(n^2) algorithm; but C
is not C++ (for which, for some bizarre reason, some of us are
actually grateful
).
