Lesson 2.1
Asymptotic Notation
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.
← Advanced CS Study Guide
Code Scholars Tutoring · Advanced CS
Unit 2: Sorting, Searching, and Efficiency
Lessons and exercises
Where the course starts comparing solutions rather than just producing them. The sorts are the vehicle; asymptotic reasoning is the actual subject.
Lesson 2.2
Comparison Sorts
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.
Lesson 2.3
Merge Sort and Quick Sort
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.
Lesson 2.4
Binary Search
Binary search halves the search range each step and therefore costs log n, but it requires sorted input as a precondition.
Need help with this topic?
Work through questions with a tutor and get help with the steps you find difficult.
Get help with this topic