Information Technology Reference
In-Depth Information
Describe data structures carefully. This does not mean that you should give record
definitions in a pseudo-language; instead, use, say, a simple mathematical notation
to unambiguously specify the structure.
Each element is a triple
(string, length, positions)
in which
positions
is a sequence of byte offsets at which
string
has
been observed.
Be consistent. When presenting several algorithms for the same task, they should as
far as possible be defined over the same input and output. It may be the case that
some of the algorithms are more powerful than the others—perhaps they can process
a richer input language, for example. Variations of this kind should be made explicit.
Asymptotic Cost
The performance of algorithms is often measured by asymptotic analysis; the reader
should learn how an algorithm behaves as the scale of the problem changes. Big-O
notation can be defined as follows: a function
f
(
n
)
is said to be O
(
g
(
n
))
—that is,
g
(
n
)
is an upper bound of
f
(
n
)
—if for some constants
c
and
k
we have
f
(
n
)
≤
c
·
g
(
n
)
>
(
)
(
(
))
(
)
(
(
))
(
)
(
(
))
for all
n
k
.If
f
n
is O
g
n
and
g
n
is O
f
n
, then
f
n
is
g
n
; that is,
is used to define functions that grow asymptotically at the same rate.
A function
f
(
n
)
is o
(
g
(
n
))
if
f
is O
(
g
(
n
))
but not
(
g
(
n
))
. Likewise,
and
ω
are used to describe lower bounds. Other definitions are given by some authors,
and the use of the notation is slightly inconsistent, so it is helpful to define what you
mean by, for example,
. For a precise discussion, consult an algorithms text.
Big-O notation is also used in another, less formal sense, to mean
the asymptotic
cost
rather than
an upper bound on the asymptotic cost
. An author might write that
“comparison-based sorting takes
O
(
g
(
n
))
(
n
log
n
)
time” or that “linear insertion sort always
takes at least
O
time”; which, although an abuse, is perfectly clear and has stronger
emphasis than “linear insertion sort has asymptotic cost
(
n
)
”. But beware of loose
usage that could be misunderstood. When you describe an algorithm as “quadratic”,
some readers may assume that quadratic worst case is meant, while others may
assume that it is quadratic in all cases. Similarly be careful with “constant”, “linear”,
“logarithmic”, and “exponential”.
A related cause of occasional confusion is the distinction between the intrinsic
asymptotic cost of a problem and the properties of a specific algorithm for the prob-
lem. For some problems, a theoretical limit is known, which is usually a lower bound
on the asymptotic cost of any algorithm that solves the problem. Specific algorithms
may not approach this lower bound. Unhelpfully—and incorrectly—authors have
been known to write statements of the form “the problem's complexity is
O
(
n
)
(
f
(
n
))
”,
implicitly meaning intrinsic cost, even though
O
(
·
)
is an upper bound and intrinsic
cost is (usually) a lower bound.
