This chapter lays the groundwork for thinking like an algorithms practitioner. It defines an algorithm as a clear set of steps for solving a task and explains why some are worth learning: they’re fast, broadly useful, or both. You’re introduced to a consistent approach—describe an algorithm, walk through an example, analyze its running time, and map it to other problems—while also learning to weigh tradeoffs (like choosing between data structures or sorting methods). The chapter connects these ideas to real applications, previewing how algorithms power tasks from login checks to routing and recommendations, and sets light prerequisites (basic algebra and familiarity with a programming language; examples use Python).
The centerpiece is binary search, a strategy for finding an item in a sorted collection by repeatedly checking the middle and discarding half the remaining candidates. Through intuitive examples (phone books, dictionaries, number guessing), the chapter contrasts binary search with simple linear search: the former needs only about log2 n steps in the worst case, while the latter can require up to n. This dramatic difference means searches over huge datasets can shrink from billions of checks to just a few dozen—provided the data is sorted—illustrating how algorithm choice dominates performance.
To reason about performance rigorously, the chapter introduces big O notation, which measures how running time grows with input size rather than in seconds. You learn the idea of worst-case analysis and see why growth rates matter: O(log n) scales far better than O(n), and both are vastly preferable to quadratic O(n²) or factorial O(n!) time. Through simple analogies (like folding paper to double boxes) and cautionary tales (a rocket-landing scenario and the traveling salesperson problem), the chapter shows how to estimate costs, avoid misleading intuitions, recognize when problems are intractable, and choose or approximate solutions wisely.
Looking for companies in a phone book with binary search
A bad approach to number guessing
Eliminate half the numbers every time with binary search.
Run times for search algorithms
Running time for simple search vs. binary search with a list of 100 elements
Run times grow at very different speeds!
What big O notation looks like
What’s a good algorithm to draw this grid?
Drawing a grid one box at a time
Drawing a grid in four folds
The number of operations increases drastically.
Recap
- Binary search is a lot faster than simple search as your array gets bigger.
- O(log n) is faster than O(n), and it gets a lot faster once the list of items you’re searching through grows.
- Algorithm speed isn’t measured in seconds.
- Algorithm times are measured in terms of growth of an algorithm.
- Algorithm times are written in big O notation.
FAQ
What is an algorithm, and what does Chapter 1 focus on?
An algorithm is a set of instructions for accomplishing a task. Chapter 1 gives you a foundation for the rest of the book by introducing binary search (your first algorithm) and showing how to reason about performance with Big O notation.
How does binary search work?
Binary search finds an item in a sorted list by repeatedly guessing the middle element and eliminating half of the remaining items each time:
- Start with low = start of list and high = end of list.
- Check the middle element.
- If it’s the target, you’re done. If it’s too high, move high to mid − 1; if too low, move low to mid + 1.
- Repeat until found or the search space is empty.
Why must the list be sorted for binary search?
Only a sorted list lets you decide which half to discard after checking the middle element. If the list isn’t sorted, “too high” or “too low” gives no information about where the target could be.
How does binary search compare to simple (linear) search?
- Simple search: checks items one by one; worst-case time is O(n).
- Binary search: halves the search space each step; worst-case time is O(log n).
- Example: Searching 240,000 words—simple search could take 240,000 steps; binary search takes about 18.
How many guesses does binary search need in practice?
- At most log2(n) guesses for n items.
- 100 items → ≤ 7 guesses.
- 1,000,000,000 items → ≈ 30–32 guesses.
- 128 names → ≤ 7 guesses; double the list size → just one more guess.
What is Big O notation and why is it useful?
Big O describes how the number of operations grows as input size increases. It lets you compare algorithm efficiency independently of hardware and constant factors. For example, binary search is O(log n) and simple search is O(n).
What does “log” mean in this chapter?
Unless stated otherwise, log means log base 2 (log2). It answers “How many times do we double 1 to reach n?” For example, log2(8) = 3 because 23 = 8.
Does Big O describe worst-case or average-case time?
In Chapter 1, Big O is used for worst-case analysis—an upper bound on running time. Average-case behavior is also important (discussed later in the book), but worst case gives a guarantee your algorithm won’t be slower than that bound.
What are the most common Big O runtimes introduced here?
- O(log n): binary search
- O(n): simple search
- O(n log n): fast sorts (e.g., quicksort)
- O(n²): slow sorts (e.g., selection sort)
- O(n!): brute-force solutions (e.g., traveling salesperson)
What is the traveling salesperson problem and why is it hard?
Given n cities, find the shortest route visiting each once and returning to start. The brute-force solution checks all n! permutations—factorial time (O(n!)), which explodes even for modest n. There’s no known fast exact algorithm; in practice, we use approximations.
Grokking Algorithms, Second Edition ebook for free
