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 deter-
mine 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 bet-
ter 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)
