CSE 143, Quiz 9                                                     10 Aug 2000

name ____________________________________________ student number _______________

                                                              section __________

This quiz is closed book, closed notes.  You have six minutes.  Write your
answers neatly on this page.

1.  For each sorting algorithm below, three sequences of numbers are listed.
    Choose a sequence which results in worst-case (longest) running time and
    indicate the resulting running time using big-O notation in terms of n
    (where n == the number of numbers in the sequence).

    Assume implementations as presented in lecture, and that the result of
    sorting is the input sequence in INCREASING order, i.e. 0 1 2 3 ... 9.  Note
    that more than one of the given sequences might result in worst-case running
    time.

    insertion sort

      a.  0  1  2  3  4  5  6  7  8  9  (increasing order)
      b.  9  8  7  6  5  4  3  2  1  0  (decreasing order)
      c.  6  2  8  7  4  3  0  5  9  1  (random order)
   

      worst-case sequence:  _____       running time:  O(_______________)

    quicksort (with first-element pivot)

      a.  0  1  2  3  4  5  6  7  8  9  (increasing order)
      b.  9  8  7  6  5  4  3  2  1  0  (decreasing order)
      c.  6  2  8  7  4  3  0  5  9  1  (random order)
   

      worst-case sequence:  _____       running time:  O(_______________)
    

2.  What is the BEST-case running time for quicksort?  (Again, use big-O
    notation.)