Unit 2 · Heavy
Where the course starts comparing solutions rather than just producing them. The sorts are the vehicle; asymptotic reasoning is the actual subject.
What a strong answer looks like
A strong Unit 2 answer names the case being described, drops constants, and compares growth rather than reporting a measured time.
Know
Big-O bounds growth from above, big-Omega from below, and big-Theta applies when both match. Constants and lower-order terms are discarded because they do not affect growth.
Apply
Reduce a cost expression to its dominant term, then name the case you are describing.
Watch out
Reporting O(3n squared) as if the constant mattered, or conflating worst case with big-O.
Study move
Reduce four cost expressions to their tightest bound and say which case each describes.
Know
Any sort that works by comparing pairs needs at least n log n comparisons in the worst case, which is why merge sort is asymptotically optimal and bubble sort is not.
Apply
Classify a sort by its worst, average, and best case, and by whether it is stable and in place.
Watch out
Quoting one complexity for a sort that has different worst and average behavior, as quick sort does.
Study move
Build a table of worst, average, best, stability, and space for four sorts.
Know
Merge sort always splits evenly and always costs n log n, but needs linear extra space. Quick sort partitions in place and is usually faster, but degrades to quadratic on a bad pivot.
Apply
Choose merge sort when worst-case guarantees matter and quick sort when average performance and memory do.
Watch out
Claiming quick sort is always faster. On sorted input with a naive pivot it is the slowest of the two by a wide margin.
Study move
Trace quick sort on already-sorted input with a first-element pivot and count the partitions.
Know
Binary search halves the search range each step and therefore costs log n, but it requires sorted input as a precondition.
Apply
Verify the sorted precondition, then compute the midpoint in a way that cannot overflow.
Watch out
Running binary search on unsorted data, which returns a wrong answer confidently rather than failing.
Study move
Trace binary search on a sorted array, writing the range bounds at each step.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Given a list that is nearly sorted and must be sorted stably with minimal extra memory, choose an algorithm and justify the choice against two alternatives.
