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.)
................................................................................
1. insertion sort: b, O(n2)
quicksort: either a or b, O(n2)
2. O(n log n)