Let us turn to another problem
which could involve N! steps. This is finding
the determinant of an N by N matrix. The definition of a determinant tells us
to find all possible ways of taking an element from each row of the matrix
(these are permutations, and there are N! of them), take the product of these
elements, and sum all N! products (with minus signs, if the permutation is
"odd"). A program which does this literally is a bad program, and will take
the lifetime of the universe to compute a 25 by 25 determinant. (Never mind
that it is our favourite method for 2 by 2 or 3 by 3 determinants.) However,
if we convert the matrix to triangular form, the determinant can be found by
simply multiplying the diagonal elements. Triangularization, can be done in
N^3 steps (forgetting constant factors), which is entirely tractable.