Java Reference
In-Depth Information
The third definition, , called
Big-Theta
, says that the
growth rate of equals the growth rate of . For instance, the max-
imum subsequence algorithm shown in Figure 5.5 runs in time. In
other words, the running time is bounded by a quadratic function, and this
bound cannot be improved because it is also lower-bounded by another qua-
dratic function. When we use Big-Theta notation, we are providing not only
an upper bound on an algorithm but also assurances that the analysis that
leads to the upper bound is as good (tight) as possible. In spite of the addi-
tional precision offered by Big-Theta, however, Big-Oh is more commonly
used, except by researchers in the algorithm analysis field.
T
( )
=
Θ
(
F
( )
)
Big-Theta
is similar
to equal to, when
growth rates are
being considered.
T
( )
F
( )
Θ
N
( )
The final definition, , called
Little-Oh
, says that the
growth rate of is strictly less than the growth rate of . This func-
tion is different from Big-Oh because Big-Oh allows the possibility that the
growth rates are the same. For instance, if the running time of an algorithm is
, then it is guaranteed to be growing at a slower rate than quadratic
(that is, it is a
subquadratic algorithm
). Thus a bound of
T
( )
=
oF
( )
(
)
Little-Oh
is similar
to less than, when
growth rates are
being considered.
T
( )
F
( )
oN
( )
oN
( )
is a better
bound than
Θ
N
( )
. Figure 5.9 summarizes these four definitions.
A couple of stylistic notes are in order. First, including constants or low-
order terms inside a Big-Oh is bad style. Do not say or
. In both cases, the correct form is .
Second, in any analysis that requires a Big-Oh answer, all sorts of shortcuts
are possible. Lower-order terms, leading constants, and relational symbols are
all thrown away.
Now that the mathematics have formalized, we can relate it to the analysis
of algorithms. The most basic rule is that
the running time of a loop is at most
the running time of the statements inside the loop (including tests) times the
number of iterations
. As shown earlier, the initialization and testing of the
loop condition is usually no more dominant than are the statements encom-
passing the body of the loop.
Throw out leading
constants, lower-
order terms, and
relational symbols
when using Big-Oh.
T
( )
=
O
2
N
2
(
)
T
( )
=
ON
2
(
+
N
)
T
( )
=
ON
( )
figure 5.9
Meanings of the
various growth
functions
Mathematical Expression
Relative Rates of Growth
T
( )
=
OF
( )
(
)
Growth of
T
( )
is
≤
growth of
F
( )
.
T
( )
=
Ω
(
F
( )
)
Growth of
T
( )
is
≥
growth of
F
( )
.
T
( )
=
Θ
(
F
( )
)
Growth of
T
( )
is
=
growth of
F
( )
.
T
( )
=
oF
( )
(
)
Growth of
T
( )
is
<
growth of
F
( )
.
Search WWH ::
Custom Search