SI433 Class 9: Lower Bounds for Sorting, and Adieu to Divide and Conquer

Reading
Section 8.1 discusses why Theta(n log(n)) is best-possible for sorting. This page provides several divide & conquer examples including that of integer multiplication due to Karatsuba. The same technique is used with matrix multiplication, and that algorithm is due to Strassen. Karatsuba discovered his method in the early 1960's. This link offers one comparison of Karatsuba and the grade school method.

Homework
Consider the problem of sorting a large list of integers, all of which lie in the range 0 ... 9. Counting Sort is a special kind of sorting method that solves problems like this. The idea is to first go through the list, keeping track of the number 0's in the array, the number of 1's, the number of 2's, ...., up to the number of 9's. This information is then used to determine in O(1) time what position any given element of the input list is at in sorted order. Here's psuedo code for couting sort: Let A be the input array of n numbers in the range 0 to 9.
C <- an array of 10 integers all initialized to zero
B <- an array of n numbers (this will be the output array)

for each i from 0 to n-1 do // After this, C[x] is the number
  increment C[A[i]]         // of times x appears in A.

for each i from 1 to 9 do   // After this, C[x] is the number of elements
  C[i] <- C[i] + C[i-1]     // of A that are less than or equal to x.

for each i from n-1 downto 0 do
  B[C[A[i]] - 1] <- A[i]
  C[A[i]] <- C[A[i]] - 1
The array B then holds the original elements in sorted order.

  1. Suppose you are given the array
    A = [3 1 8 0 8 0 1 0 3 8]
    
    all of whose entries lie in the range [0..9]. This is a candidate for counting sort! What does the array C look like after the first loop? What does the array C look like after the second loop? What does the array B look like after 7 iterations through the last loop?

    Turn in: A "picture" of the array C after the first loop. A "picture" of the array C after the second loop. A "picture" of the array B after 7 iterations through the third loop (any uninitialized entries in B should be marked with an "x").

  2. Analyze the time complexity of Counting sort in terms of n, the size of the array, and N, the range of possible values. (Note: this is not a divide and conquer algorithm!)

    Turn in: A paragraph explaining how you derived the time complexity of Counting Sort. (And yes, actually state that complexity!)

Lecture
Review Homework

Showing that Theta(n lg(n)) is Best-Possible for Sorting
Section 8.1 covers the proof we'll give for why Theta(n lg(n)) is the best possible worst-case time for a general purpose sorting algorithm. This proof makes use of Stirling's Approximation, which says that:
       ______ 
n! = \/2 Pi n (n/e)^n (1 + (1/n))
	    
From Stirling's Approximation you can prove that
lg(n!) = (n lg n)

Divide & Conquer Algorithm for Integer Multiplication
We went through one last example of divide and conquer: Karatsuba's Algorithm for multiplying integers.


Asst Prof Christopher Brown
Last modified: Tue Feb 5 16:03:46 EST 2002