1. Devise an algorithm to multiply two n-bit numbers. Provide an exact best-, worst-, and average-case analysis of the number of one-bit multiplications and additions needed by your algorithm to multiply the two numbers as a function of n.

   ---

   Let the two n-bit numbers to be multiplied be represented by the n-element boolean arrays A and B; the answer will be stored in the 2n-element boolean array C.

   The heart of the algorithm is the line

   c, C[i + j] <- C[i + j] + (A[i] + c)B[j]
   

   where c is the carry bit. The carry-in bit gets added to a bit from A, and the result gets multiplied by a bit from B. The result of the multiplication is added to the contents of the corresponding bit in the product, which gives the new value of the product bit and the carry-out bit. Note that binary addition produces two bits for an answer: the sum bit and the carry bit; for example 1 + 1 = 1, 1 and 1 + 0 = 1, 0.

   The multiplication algorithm itself is a double loop with some initialization:

   1  i <- 0
   2  do i < 2n ->
   3    C[i] <- 0
   4  od
   5
   6  i <- 0
   7  do i < n
   8    c <- 0
   9    j <- 0
   10   do j < n
   11     c, C[i + j] <- C[i + j] + (A[i] + c)*B[j]
   12   od
   13   C[i + j] <- C[i + j] + c
   14 od
   

   Line 11 contributes two additions and two multiplication; line 13 contributes an addition. In this particular algorithm, there is no difference between best-, average- and worst-case analysis: they all incur 2n² multiplications and 2n² + n additions.

   An alternative algorithm takes advantage of the fact the if B[j] is zero, the inner loop doesn't do anything:

   i <- 0
   do i < 2n ->
    C[i] <- 0
   od
   
   i <- 0
   do i < n
     if B[j] = 1
       c <- 0
       j <- 0
       do j < n
         c, C[i + j] <- C[i + j] + A[i] + c
       od
       C[i + j] <- C[i + j] + c
     fi
   od
   

   For this algorithm, the best case occurs when B is zero, in which case no multiplications or additions are done. The worst case occurs when B contains all ones, in which case the number of multiplications is zero and the number of additions are the same as they were for the previous algorithm. The average case is difficult to analyze. For simplicity, assume half the bits in B are zero and the other half one. With this assumption, the algorithm still does zero multiplications and 2n/2² + n/2 additions.

   ---

2. True or false: sum(k = 1 to n, 2(k) - 1) = Theta(n). Justify your answer.

   ---

   False:

   sum(k = 1 to n, 2k - 1)	=	2sum(k = 1 to n, k) - sum(k = 1 to n, 1)
   	=	2(n(n - 1)/2) - n
   	=	Theta(n2) - n

   which is not in Theta(n).

   ---

3. Given the algorithm

   count_odds(A)
     odds <- 1
     i <- 0
     do i < |A|
       if odd(A[i])
         odds <- odds*A[i]
       i <- i + 1
     od
   

   provide asymptotic estimates of the number of multiplications performed by count_odds() as a function of the size of A. You should provide best-, average-, and worst-case asymptotic analysises.

   ---

   Because the analysis is for explicit multiplication, many of the statements in the algorithm are irrelevant:

   count_odds(A)
     do i < |A|
       if odd(A[i])
         O(1)
     od
   

   None of the remaining operations (comparison, array length, odd(), and array access) requires explicit multiplications.

   The worst case occurs when A contains all odd elements, in which case the number of multiplications is Theta(n). The best case occurs when A contains no odd elements, in which case the number of explicit multiplications is Theta(1). For the average case, assume A has the same distribution of even and odd numbers as the integers: half are odd and half are even. With this assumption, the number of explicit multiplications is Theta(n).

   ---

4. True or false: Theta(min(f(n), g(n)) = Theta(max(f(n), g(n))). Justify your answer.

   ---

   False. Consider Theta(min(n², n)). Because there exists non-negative real constants c₁ and c₂ and non-negative integer N such that, for all n >= N,

   c₁min(n², n) <= n <= c₂min(n², n)

   n = Theta(min(n², n)).

   Now consider Theta(max(n², n)). For all positive integers n, n² >= n and max(n², n) = n². There exist no non-negative real numbers c₁ and c₂ such that

   c₁n² <= n <= c₂n²

   for any positive n and n is not in Theta(max(n², n)).

   Because Theta(min(n², n)) contains an element not in Theta(max(n², n)), the two sets are not equal.

   ---

This page last modified on 24 March 2000.