Java Reference
In-Depth Information
Suppose
T
1
( )
=
OF
( )
(
)
and
T
2
( )
=
OF
( )
(
)
. Which of
5.3
the following are true?
a.
b.
c.
d.
T
1
( )
T
2
( )
=
T
1
( )
T
2
( )
+
OF
( )
(
)
=
T
1
( )
T
2
( )
-
OF
( )
(
)
⁄
=
O
( )
T
1
( )
=
OT
2
( )
(
)
Group the following into equivalent Big-Oh functions:
x
2
,
5.4
x
2
+
x,
x
2
-
x,
(
x
3
/ (
x
- 1)).
x,
and
Programs
A
and
B
are analyzed and are found to have worst-case run-
ning times no greater than
5.5
150
N
log
N
and
, respectively. Answer
2
the following questions, if possible.
a.
Which program has the better guarantee on the running time for
large values of
N
(
N >
10,000)?
b.
Which program has the better guarantee on the running time for
small values of
N
(
N <
100)?
c.
Which program will run faster
on average
for
N =
1,000?
d.
Can program
B
run faster than program
A
on
all
possible inputs?
Solving a problem requires running an
O
(
N
)
algorithm and then afterwards
5.6
a second
O
(
N
)
algorithm. What is the total cost of solving the problem?
Solving a problem requires running an
ON
( )
algorithm and then
5.7
afterwards an
O
(
N
)
algorithm. What is the total cost of solving the
problem?
Solving a problem requires running an algorithm, and then per-
forming
N
binary searches on an
N
-element array, and then running
another
O
(
N
)
5.8
O
(
N
)
algorithm. What is the total cost of solving the problem?
For the binary search routine in Figure 5.11, show the consequences
of the following replacement code fragments:
a.
5.9
Line 13: using the test
low < high
b.
Line 15: assigning
mid = low + high / 2
c.
Line 18: assigning
low = mid
d.
Line 20: assigning
high = mid
IN THEORY
5.10
For the typical algorithms that you use to perform calculations by
hand, determine the running time to
a.
Add two
N
-digit integers
b.
Multiply two
N
-digit integers
c.
Divide two
N
-digit integers
Search WWH ::
Custom Search