Lower Bounds & Linear-time Sorts

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

• Define what is meant by comparison-based algorithms.
• Relate the process of any comparison-based algorithm to a decision tree.
• Understand and explain what lower bounds are for.
• Justify $\Omega(\lg n)$ is the lower bound for comparison-based searching algorithms.
• Justify $\Omega(n \lg n)$ is the lower bound for comparison-based sorting algorithms.
• Identify which comparison-based searching/sorting algorithms are optimal.
• Understand and explain how we can beat $\Omega(n \lg n)$ lower bound in linear-time sorting algorithms.
• Explain and trace Counting sort, Bucket sort, and Radix sort, on a given sequence of data.
• Justify the time and space complexity of these algorithms in the worst case, based on the data size and data range.

This chapter does not have starter/solution code.