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 means by comparison-based algorithms.
• 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.