Page 250 - Discrete Mathematics and Its Applications

3.3 Complexity of Algorithms 229

offer little help in overcoming the complexity of algorithms of exponential or factorial time
complexity. Because of the increased speed of computation, increases in computer memory, and
the use of algorithms that take advantage of parallel processing, many problems that were con-
sidered impossible to solve five years ago are now routinely solved, and certainly five years from
now this statement will still be true. This is even true when the algorithms used are intractable.

Exercises

4
2
1. Give a big-O estimate for the number of operations with x and successively squaring (to find x ,x , and so
(where an operation is an addition or a multiplication) on). Is this a more efficient way to find x 2 k than by mul-
used in this segment of an algorithm. tiplying x by itself the appropriate number of times?
t := 0 9. Give a big-O estimate for the number of comparisons
for i := 1 to 3 used by the algorithm that determines the number of 1s
for j := 1 to 4 in a bit string by examining each bit of the string to deter-
t := t + ij mine whether it is a 1 bit (see Exercise 25 of Section 3.1).
2. Give a big-O estimate for the number additions used in ∗ 10. a) Show that this algorithm determines the number of 1
this segment of an algorithm. bits in the bit string S:
t := 0 procedure bit count(S: bit string)
for i := 1 to n count := 0
for j := 1 to n while S = 0
t := t + i + j count := count + 1
S := S ∧ (S − 1)
3. Give a big-O estimate for the number of operations,
return count {count is the number of 1s in S}
where an operation is a comparison or a multiplication,
used in this segment of an algorithm (ignoring compar- Here S − 1 is the bit string obtained by changing the
isons used to test the conditions in the for loops, where rightmost 1 bit of S to a 0 and all the 0 bits to the right
a 1 ,a 2 , ..., a n are positive real numbers). of this to 1s. [Recall that S ∧ (S − 1) is the bitwise
m := 0 AND of S and S − 1.]
for i := 1 to n b) How many bitwise AND operations are needed to find
for j := i + 1 to n the number of 1 bits in a string S using the algorithm
m := max(a i a j ,m) in part (a)?
4. Give a big-O estimate for the number of operations, 11. a) Suppose we have n subsets S 1 ,S 2 ,...,S n of the set
where an operation is an addition or a multiplication, used {1, 2,...,n}. Express a brute-force algorithm that de-
in this segment of an algorithm (ignoring comparisons termines whether there is a disjoint pair of these sub-
used to test the conditions in the while loop). sets. [Hint: The algorithm should loop through the
subsets; for each subset S i , it should then loop through
i := 1 all other subsets; and for each of these other subsets
t := 0 S j , it should loop through all elements k in S i to de-
while i ≤ n termine whether k also belongs to S j .]
t := t + i b) Give a big-O estimate for the number of times the
i := 2i
algorithm needs to determine whether an integer is in
5. How many comparisons are used by the algorithm given one of the subsets.
in Exercise 16 of Section 3.1 to find the smallest natural
12. Consider the following algorithm, which takes as input a
number in a sequence of n natural numbers?
sequenceofnintegersa 1 ,a 2 ,...,a n andproducesasout-
6. a) Use pseudocode to describe the algorithm that puts the put a matrix M ={m ij } where m ij is the minimum term
first four terms of a list of real numbers of arbitrary in the sequence of integers a i ,a i+1 ,...,a j for j ≥ i and
length in increasing order using the insertion sort. m ij = 0 otherwise.
b) Show that this algorithm has time complexity O(1) in initialize M so that m ij = a i if j ≥ i and m ij = 0
terms of the number of comparisons used.
otherwise
7. Suppose that an element is known to be among the first
for i := 1 to n
four elements in a list of 32 elements. Would a lin-
for j := i + 1 to n
ear search or a binary search locate this element more for k := i + 1 to j
rapidly?
m ij := min(m ij ,a k )
8. Given a real number x and a positive integer k, determine return M={m ij } {m ij is the minimum term of
the number of multiplications used to find x 2 k starting a i ,a i+1 ,...,a j }