ANSWERS TO EXERCISES ON COMPLEXITY


 1. Depends on the computer and the compiler!  These times are on a DEC Alpha.

    % gcc billion.c
    time a.out 
    313.35u 1.16s 10:36 49% 0+1k 1+0io 14pf+0w

    % gcc -O9 billion.c
    time a.out
    30.64u 0.20s 1:02 49% 0+1k 1+0io 14pf+0w

    % cc billion.c
    time a.out
    289.52u 1.31s 9:51 49% 0+1k 3+0io 14pf+0w

    % cc -O9  billion.c
    time a.out
    289.49u 0.96s 9:45 49% 0+1k 10+0io 16pf+0w

    % lcc billion.c
    time a.out 
    45.79u 0.16s 1:31 50% 0+0k 2+0io 2pf+0w


 2. (a)  O(N).  Computing strlen(word) takes N steps. The body of
         the for loop is executed N times.  Each statement in the
         body of the for loop takes O(1) time.

    (b)  O(N^2).  Computing strlen(word) takes N steps. This
         is computed from scratch 2N times, once in the for loop
         test condition, and once in the body of the for loop.

         There are plenty of C program out there that are extremely
         slow on long strings exactly for this reason!
 
 3.  O(N).  The body of the loop is executed N times. The body
     of the loop has 3 statements.  Thus there are a total of 
     3N steps; in big-Oh notation this is O(N).

     There are plenty of C programs out there that are extremely
     slow because they use an N^2 shuffling algorithm.

 4. (a)  O(N^2).  Each time a new point is inserted, the algorithm
         traverses through the current linked list. When the kth
         point is added, there are k-1 points already on the list.
         For each of these k-1 points, we need to compute the Euclidean
         distance to the new point.  Thus, inserting the kth point
         takes O(k) steps.  Summing up over all N points, we get
         1 + 2 + 3 + . . . + N-1 = O(N^2).

   (b)   O(N^2).  Basically the same as above.  Instead of computing
         the distance from one of the k-1 points to the new point,
         we compute the change in tour length.  This involves 3 Euclidean
         distance computations instead of 1, but this constant is
         buried in the big Oh notation.

         Note that if you recompute the tour length each time from
         scratch (instead of computing the change in tour length),
         you would get a O(N^3) algorithm.


 5.  Sort the integers using mergesort in O(N log N) steps.
     The median is now stored in array element N/2.  The
     mode can also be found easily since now all equal values
     are stored consecutively (Recall the loops exercise that finds
     the longest streak of consecutive values).

 6. (a)  See distribution sort in the Notes on Arrays (or  Question 4
         from Spring 2000, Midterm 1).  The assumption that the integers
         are in the range 0 to 99 is crucial, and enables us to beat the
         N log N lower bound.  Recall this lower bound assumes that the
         algorithm only performs comparison and swap operations.

    (b)  Once the integers are sorted, we can find the mode or median
         as in the previous question.

         Using lots of cleverness, the median can still be computed
         in O(N) time even without the assumption that the integers
         lie in the range 0 to 99. See COS 226.

 7. (a)  Brute force: compute the difference between every pair of integers,
         and keep track of the smallest value.

         Better solution:  sort the integers using an O(N log N). Now, the
         closest pair occurs consecutively within the list, and it is easy
         to find in O(N) time.


 8. Hint 1: sort.
    Hint 2: sort.