Algorithm analysis - Data Structures and Problem Solving Using Java - page 221

Occasionally, multiplying the sizes of nested loops can give an over-
estimate for the Big-Oh running time. This result happens when an
innermost loop is infrequently executed. Repeat Exercise 5.20 for the
following program fragment:

5.21

for( int i = 1; i <= n; i++ )
for( int j = 1; j <= i * i; j++ )
if( j % i == 0 )
for( int k = 0; k < j; k++ )
sum++;

5.22

In a court case, a judge cited a city for contempt and ordered a fine of
$2 for the first day. Each subsequent day, until the city followed the
judge's order, the fine was squared (that is, the fine progressed as fol-
lows: $2, $4, $16, $256, $65536, . . . ).
a. What would be the fine on day N ?

b. How many days would it take for the fine to reach D dollars (a

Big-Oh answer will do)?

Unlucky Joe has been in companies that keep getting bought out by
other companies. Every time Joe's company is bought out, it is
always swallowed up by a larger company. Joe is now in a company
with N employees. What is the maximum number of different compa-
nies that Joe has worked for?

5.23

1 d

x

x

Prove Theorem 5.5. Hint : Show that

N

---

<

N

----- . Then show a sim-

5.24

∑

∫

2 1

ilar lower bound.

Construct an example whereby an interpolation search examines
every element in the input array.

5.25

Analyze the cost of an average successful search for the binary search
algorithm in Figure 5.11.

5.26

Integers in Java range from -2 31 to 2 31 - 1. Consequently, if we have
a large array with more than 2 30 elements, computing the midpoint of
a subarray using mid=(low+high)/2 will cause low+high to overflow the
integer range if the midpoint resides past array index 2 30 .
a.

5.27

How large is 2 30 ?

b. Show that ( low +(high-low)/2 ) is a computationally equivalent

calculation that does not overflow in this situation.

c. How large can an array be using the modification suggested in

part (b)?