CS 2401, Spring 2009

Typical mistakes for Test 3

Problem 1: worst case complexity cannot be smaller than the average case; some
seem to confuse worst-case with best-case, and reported O(n) as the worst-case
complexity, smaller than the average-case complexity O(n^2)

Problem 2: in selection sort, once we found the next smallest element among the
non-sorted ones, we swap it into its correct place; one swap is enough, we do
not move the whole array just to place one element

Problem 2: worst-case complexity and average-case complexity have the same
asymptotic, but it does not mean that they are equal, they are different, they
just have the same asymptotic O(n^2)

Problem 8: for linear search, we know exactly the worst-case complexity -- it
is n comparisons, and average-case complexity which is (n+1)/2; the answer O(n)
is technically correct, but in this case, we know better than that

Problem 9: while most codes in Problem 10 were correct, the tracing in Problem
9 is wrong in many tests; for example, if we know that the item that we are
searching is smaller than the value at midpoint, then we search to the left of
the midpoint, so the new value of last is mid - 1, not mid