8 1 A Taste of Things to Come
two digits, compute the carry, if necessary, and add it to the next
position. All that requires at most 3 operations, making it
3([log10(n)] + 1)
in total. It is convenient to say succinctly that the time complexity
of addition is
O(log10(n)).
Notice further that a change of the basis of the logarithm amounts
to multiplication of its value by a constant; hence we can use any
basis (actually, computer scientists prefer base 2, since everything
is done in binary numbers) and just write O(log n).
Similarly, the multiplication of two integers has time complex-
ity at most
O(log2
n), or quadratic time complexity, while the mul-
tiplication of two n × n matrices with integer entries, each smaller
than m, requires at most
O(n3
log2
m) operations. I do not consider
here various interesting and useful ways to speed up the standard
procedures; see the classical book by Knuth [372] for a very com-
prehensive survey of the huge body of knowledge on fast practical
algorithms.
Why is the class P of polynomial time algorithms so important?
From a practical point of view, many known polynomial time al-
gorithms cannot be used on modern computers now or in the near
future, since the constant in O( ), or the power of the polynomial
involved, may be too big for the computation to be completed in any
feasible amount of time.
As frequently happens in mathematics, P is being studied be-
cause it is robust. The actual degree d in the bound O(nd) for
complexity depends on data structures and other computer science
tricks used; but if an algorithm can be implemented as polynomial
time one way, it remains polynomial time in all reasonable imple-
mentations, and this allows us to work at the theoretical level and
ignore the details.
Also, there is a school of thought holding that the existence of a
polynomial time algorithm should normally suggest the existence
of a good and practically feasible polynomial time algorithm. This
is how Neal Koblitz (one of the founders of algebraic cryptography)
put it in [373, p. 37]:
The experience has been that if a problem of practical inter-
est is in P, then there is an algorithm for it whose running
time is bounded by a small power of the input length.
Koblitz’s statement is a metamathematical thesis describing a big
class of especially nice
algorithms.5
In the next section, I will try to
describe even nicer algorithms—but, unfortunately, these are less
versatile and less applicable than polynomial time algorithms.
Previous Page Next Page