Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
CHAPTER 2
Algorithm Analysis
2.1 2/N, 37,
N
, N, N log log N, N log N, N log(N2), N log2 N, N1.5, N2, N2 log N, N3, 2N/2, 2N.
N log N and N log (N2) grow at the same rate.
2.2 (a) True.
2.3 We claim that N log N is the slower growing function. To see this, suppose otherwise. Then,
log N
N
would grow slower than log N. Taking logs of both sides, we find that, under this assumption,
2.4 Clearly,
12
log (log )
kk
N o N=
if k1 < k2, so we need to worry only about positive integers. The claim is
2.5 Let f(N) = 1 when N is even, and N when N is odd. Likewise, let g(N) = 1 when N is odd, and N when N is
even. Then the ratio f(N)/g(N) oscillates between 0 and inf.
(III) The running time is O(N3).
(IV) The running time is O(N2).
2.8 (a) It should be clear that all algorithms generate only legal permutations. The first two algorithms have tests
to guarantee no duplicates; the third algorithm works by shuffling an array that initially has no duplicates, so
(b) For the first algorithm, the time to decide if a random number to be placed in a[i] has not been used
earlier is O(i). The expected number of random numbers that need to be tried is N/(N – i). This is obtained as
follows: i of the N numbers would be duplicates. Thus the probability of success is (N – i)/N. Thus the
(c,d) The running times should agree with the preceding analysis if the machine has enough memory. If not,
the third algorithm will not seem linear because of a drastic increase for large N.
2.9 Algorithm 1 at 10,000 is about 38 minutes and at 100,000 is about 26 days. Algorithms 1–4 at 1 million are
approximately: 72 years, 4 hours, 0.7 seconds, and 0.03 seconds respectively. These calculations assume a
machine with enough memory to hold the entire array.
2.10 (a) O(N)
2.11 (a) Five times as long, or 2.5 ms.
2.12 (a) 12000 times as large a problem, or input size 1,200,000.
2.13 (a) O(N2).
(b) O(N log N).
2.15 Use a variation of binary search to get an O(log N) solution (assuming the array is reread).
2.20 (a) Test to see if N is an odd number (or 2) and is not divisible by
3, 5, 7, , .N
2.21 The running time is proportional to N times the sum of the reciprocals of the primes less than N. This is O(N
log log N). See Knuth, Volume 2.
2.24 For N = 0 or N = 1, the number of multiplies is zero. If b(N) is the number of ones in the binary
representation of N, then if N > 1, the number of multiplies used is
log ( ) 1N b N+−
2.25 (a) A.
2.26 (a) Recursion is unnecessary if there are two or fewer elements.
(b) One way to do this is to note that if the first N – 1 elements have a majority, then the last element cannot
2.27 Start from the top-right corner. With a comparison, either a match is found, we go left, or we go down.
Therefore, the number of comparisons is linear.
2.28 (a, c) Find the two largest numbers in the array.
a[i], reset the current low point to i. Start with i at index 0, j at index 0. j just scans the array, so the running
time is O(N).
2.29 Otherwise, we could perform operations in parallel by cleverly encoding several integers into one. For
