What is the worst case time for quicksort, to within a constant factor? O(n2)
What is the best case time for quicksort, to within a constant factor? O(n log(n))
Show the result of sorting each decimal digit column, using radix sort, on the list [245, 163, 207, 109, 243].
245 163 207 109 163 243 109 163 207 245 243 207 109 207 245 243 243 109 163 245
The first column is the original list. The second column is the list after sorting by the rightmost digit. The third column is the result of sorting by the middle digit, and the last column is obtained by sorting the the leftmost digit. Each sort is stable.
Explain how to tell whether a list of n numbers has two occurrences of the same number in O(n log(n)) time.
Sort the list, then compare adjacent members. If any two adjacent members are the same, say that there is a duplicate. Otherwise, say that there is no duplicate.
What is the definition of a stable sorting algorithm?
A sorting algorithm is stable if it does not rearrange equal values.
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?
It isn't a comparison algorithm.
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.
n0.95log2(n) grows asymptotically slower than n, which is lower than the Ω(n log(n)) lower bound for algorithms that sort by comparisons.
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?
n0.95log2(n) grows asymptotically slower than n, so the algorithm does not even have enough to look at the input list. It cannot possibly sort in less time than it takes to look at each number once.
Suppose that an algorithm performs f(n) steps, and each step takes g(n) time. How long does the algorithm take?
f(n)g(n)
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?
f(n) + g(n)
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?)
f(n) + g(f(n)). Remember that algorithm B takes time g(N) where N is the length of the input that it is given. Since algorithm A takes time f(n), and it can only write one character per step, the longest answer that it can write is f(n) characters. So the N for algorithm B is no more than f(n), and algorithm B takes no more f(n), and B takes no more than g(f(n)) time.