Java Reference
In-Depth Information
Use equalities with Big-Oh, Big-Omega, and so on. Writing that the
running time is makes no sense because Big-Oh is an upper
bound. Do not write that the running time is ; if the intention is
to say that the running time is strictly less than quadratic, use Little-Oh
notation.
4.
>
O
N
( )
<
O
N
( )
Use Big-Omega, not Big-Oh, to express a lower bound.
5.
Use the logarithm to describe the running time for a problem solved by
halving its size in constant time. If it takes more than constant time to
halve the problem, the logarithm does not apply.
6.
The base (if it is a constant) of the logarithm is irrelevant for the purposes
of Big-Oh. To include it is an error.
7.
The three maximum contiguous subsequence sum algorithms, as well as a
fourth taken from Section 7.5, are available, along with a
main
that conducts
the timing tests.
MaxSumTest.java
Contains four algorithms for the maximum subse-
quence sum problem.
BinarySearch.java
Contains the binary search shown in Figure 5.11.
The code in Figure 5.12 is not provided, but a sim-
ilar version that is part of the Collections API and
is implemented in Figure 6.15 is in
Arrays.java
as
part of
weiss.util
.
IN SHORT
Balls are drawn from a box as specified in Theorem 5.1 in the combi-
nations given in (a) - (d). What are the corresponding values of
i
,
j
,
and
k
?
a.
5.1
Red, 5, 6
b.
Blue, 5, 6
c.
Blue, 3, Red
d.
6, 5, Red
Why isn't an implementation based solely on Theorem 5.2 sufficient
to obtain a subquadratic running time for the maximum contiguous
subsequence sum problem?
5.2
Search WWH ::
Custom Search