What is the worst case time for quicksort, to within a constant factor?
What is the best case time for quicksort, to within a constant factor?
Show the result of sorting each decimal digit column, using radix sort, on the list [245, 163, 207, 109, 243].
Explain how to tell whether a list of n numbers has two occurrences of the same number in O(n log(n)) time.
What is the definition of a stable sorting algorithm?
We proved a lower bound of Ω(n log(n)) for the number of comparisons needed to sort n things using a comparison algorithm. Counting sort only takes time O(n). How does counting sort manage to do better than the lower bound?
Larry has developed an algorithm that sorts by comparisons, and his analysis concludes that it takes O(n0.95log2(n)) time. Show that either Larry's algorithm does not work or that his analysis is wrong.
What if Larry's algorithm sorts arrays of small integers, and does not rely on doing comparisons. Is it possible for his algorithm and his analysis both to be correct then?
Suppose that an algorithm performs f(n) steps, and each step takes g(n) time. How long does the algorithm take?
Suppose that an algorithm performs two steps, the first taking f(n) time and the second taking g(n) time. How long does the algorithm take?
Suppose that f(n) and g(n) are monotonically increasing functions. Suppose that algorithm A takes time f(n) on inputs of length n, and algorithm B takes time g(n) on inputs of length n. You give an input of length n to algorithm A and then take the output from algorithm A and feed that into algorithm B. What is the most time that the entire process could possibly take, as a function of n? (Hint. Algorithm A might write a long output. But it can only write one character per step. What is the longest result that it can possibly write?)