CS50 Week 3 Explained: Searching, Sorting, Big O and Recursion

Week 3 comes back to the phone book from Week 0 and makes it precise. How do we measure how fast an algorithm is? Why does sorting matter so much? And how can a function solve a problem by calling itself? This is the most "computer science" week of the course.

▶

Watch the lecture

CS50x 2026, Lecture 3: Algorithms

2 h 0 min · Harvard University · CS50 on YouTube

Watch on YouTube ↗Week page ↗Harvard's notes ↗

Jump to the key moments

1. 14:27Linear search
2. 17:40Binary search
3. 27:01Running time
4. 56:09Structs
5. 1:12:20Selection sort
6. 1:20:12Bubble sort
7. 1:29:11Recursion
8. 1:45:46Merge sort
9. 1:57:23Sort race

Searching: linear vs binary

Linear search checks each item in turn. It works on any list, but on a list of n items it might take n steps. Binary search checks the middle item, discards the half that can't contain the target, and repeats. It takes about log₂ n steps, but only if the list is already sorted. That trade-off is the setup for the rest of the lecture.

Running time and Big O

Computer scientists describe speed by how the number of steps grows as the input grows, not in seconds. Big O gives the upper bound (the worst case). Omega (Ω) gives the lower bound (the best case). Theta (Θ) applies when the two are the same. The common ones, from fastest to slowest: O(1) constant, O(log n), O(n), O(n log n), O(n²). Linear search is O(n) but Ω(1), because you might get lucky on the first item. Binary search is O(log n).

Structs: your own data types

A struct bundles related values into one new type. A person might have both a name and a number. Keeping them together means they can't get out of step, which is what happens when you keep two separate arrays and sort only one of them. You'll use structs in every problem this week.

Three sorting algorithms

• Selection sort: find the smallest remaining item and move it to the front, then repeat. It's always O(n²), even if the list is already sorted.
• Bubble sort: swap neighbouring items that are out of order, and keep passing through the list. It's O(n²) in the worst case, but it can stop early when a pass makes no swaps, so it's Ω(n) on a sorted list.
• Merge sort: split the list in half, sort each half, then merge the two sorted halves. It's O(n log n) every time, which is much faster on big lists, at the cost of extra memory.

The "Sort race" chapter at the end of the lecture shows the difference visually. Watch it even if you skip everything else.

Recursion

A recursive function calls itself on a smaller version of the same problem. It needs a base case, the smallest version, which it answers directly. Without one, it calls itself forever and crashes. Merge sort is recursive: to sort a list, sort each half (the recursive part), and a list of one item is already sorted (the base case). If you find recursion confusing, trust the smaller call to do its job and focus only on the current step.

Problem Set 3: what it asks

• Sort: you're given three compiled sorting programs and have to work out which algorithm each one uses by timing them on different inputs. There's no code to write, only experiments and reasoning.
• Plurality: finish an election program where the candidate with the most votes wins, including ties.
• One of Runoff, a ranked-choice election that eliminates the last-placed candidate round by round, or Tideman, a ranked-pairs election that Harvard itself marks as for the "very, very, very comfortable".

Where people get stuck

• Sort: test each program on sorted, reversed and random inputs. Remember which algorithm behaves differently on a list that's already sorted. That's your clue.
• Runoff: read the whole distribution code before writing anything. Most bugs come from mixing up voter indexes, rank indexes and candidate indexes. Write down what preferences[i][j] means in words.
• Tideman's lock_pairs: the hard part is refusing an edge that would create a cycle. Phrase it as a question you can answer recursively: "if I lock winner → loser, is there already a path from loser back to winner?" Draw the graph on paper for a three-candidate example.
• Choosing Tideman out of pride: Runoff is just as valid for the certificate. Do Runoff first, and come back to Tideman later if you want the challenge.

Check yourself