March 2012
Beginner
160 pages
4h 6m
English
The order of growth for a graph algorithm is usually expressed as
a function of
, the number of vertices, and
, the number of edges.
The order of growth for BFS is
, which is a convenient way to say
that the runtime grows in proportion to either
or
, whichever is “bigger.”
To see why, think about these four operations:
This happens once for each vertex, so the total cost is in
.
This happens once for each vertex, so the total cost is in
.
This happens once for each vertex, so the total cost is in
.
This happens once each edge, ...