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