Java Reference
In-Depth Information
These big-
O
running-time estimates are admittedly crude, but they do contain some
information. They will not distinguish between a running time of 5
N
5 and a running
time of 100
N
, but they do let us distinguish between some running times and so determine
that some algorithms are faster than others. Look at the graphs in Display 15.32 and
notice that all the graphs for functions that are
O
(
N
) eventually fall below the graph
for the function 0.5
N
2
. The result is inevitable: An
O
(
N
) algorithm will always run
faster than any
O
(
N
2
) algorithm, provided we use large enough values of
N
. Although
an
O
(
N
2
) algorithm could be faster than an
O
(
N
) algorithm for the problem size you
are handling, programmers have found that, in practice,
O
(
N
) algorithms perform
better than
O
(
N
) algorithms for most practical applications that are intuitively “large.”
Similar remarks apply to any other two different big-
O
running times.
+
Display 15.32
Comparison of Running Times
N
(problem size)
