Chapter 1: Introduction to algorithms
The introduction defines an algorithm and explains why the book focuses on algorithms that speed up tasks or solve interesting problems.
After this chapter you will be able to
- Algorithms and their value. Explain what an algorithm is and why some algorithms are especially useful, using the introduction’s search example to illustrate a possible speedup.
- Algorithm and data structure tradeoffs. Explain why finding an existing implementation is not enough: you still need to compare algorithms and data structures because the choice can make a big difference.
- Basic algebra and programming background. Describe the background the book expects: basic algebra, illustrated by evaluating f(x) = x × 2, and familiarity with a programming language. Explain that examples use Python, but readers who know another language can still follow along.
- Binary search inputs and results. Describe the kind of list binary search takes and what it returns when an item is found or absent. Explain how the phone-book and dictionary examples motivate starting near the middle rather than at the beginning.
- Middle Guess Elimination. Trace how binary search guesses the middle of the remaining range and uses a too-low or too-high result to eliminate half of the candidates.
- Logarithmic Search Steps. Explain the section’s worst-case step counts for binary versus simple search, including what log base 2 means here.
- Search running time comparison. Explain how the maximum number of guesses changes as a list grows for one-by-one search versus binary search, and name their running times.
- Purpose of Big O notation. Explain that Big O notation tells you how fast an algorithm is and why that information is useful when you use someone else’s algorithm.
- Different running-time growth rates. Explain why a speed comparison on a small list cannot be assumed to hold for a much larger list. Describe how simple search and binary search diverge as list size grows.
- Big O operation counts. Explain what big O notation expresses and give the section’s big O running times for simple search and binary search.
- Linear versus logarithmic grid making. Explain why drawing 16 boxes one at a time takes 16 operations and O(n) time, while folding paper to double the number of boxes each time takes four operations and O(log n) time.
- Worst-case simple search time. Explain why finding the first phone-book entry immediately does not change simple search’s O(n) run time: in the worst case, it may have to check every entry once.
- Common run time ordering. State the five common big O run times in the section’s fastest-to-slowest order and identify the examples given for them.
- Growth rather than seconds. Explain what big O measures here and why the grid’s operation counts and seconds are only an illustration.
- Exhaustive routes and factorial growth. Explain how the described solution finds the shortest route by checking every order of the cities, adding each route’s distance, and choosing the shortest. Describe why this takes n! operations for n cities and quickly becomes impractical.
- Search Speed as Lists Grow. Explain that binary search becomes much faster than simple search as the list grows, because O(log n) grows more slowly than O(n).
- Algorithm Time as Growth. Describe how the recap measures algorithm time: by how running time grows, expressed in big O notation, rather than by seconds.
Section by section
Introduction
The introduction defines an algorithm and explains why the book focuses on algorithms that speed up tasks or solve interesting problems.
- Algorithms and their value: Explain what an algorithm is and why some algorithms are especially useful, using the introduction’s search example to illustrate a possible speedup.
Why it matters: This gives you a way to recognize what an algorithm does and why choosing one can matter.
Key terms: algorithm, binary search
1.1 What you’ll learn about performance
The section explains why choosing an algorithm or data structure requires understanding tradeoffs, even when implementations are readily available.
- Algorithm and data structure tradeoffs: Explain why finding an existing implementation is not enough: you still need to compare algorithms and data structures because the choice can make a big difference.
Why it matters: Understanding tradeoffs helps you choose what to use rather than simply using what is available.
Key terms: tradeoffs, algorithm, data structure
1.2 What you’ll learn about solving problems
The section previews problems the book will address and states the background needed to follow it.
- Basic algebra and programming background: Describe the background the book expects: basic algebra, illustrated by evaluating f(x) = x × 2, and familiarity with a programming language. Explain that examples use Python, but readers who know another language can still follow along.
Why it matters: These expectations help you judge whether you’re ready to follow the examples.
Key terms: basic algebra, programming language, Python
1.3 Binary search
Introduces binary search as a way to find an item in a sorted list and contrasts it with guessing one item at a time.
- Binary search inputs and results: Describe the kind of list binary search takes and what it returns when an item is found or absent. Explain how the phone-book and dictionary examples motivate starting near the middle rather than at the beginning.
Why it matters: This establishes what problem binary search solves before the book explains its steps. - Simple search guessing cost: Explain why guessing 1, 2, 3, and so on can take many tries in the number-guessing example.
Why it matters: The slow guessing example shows why a better search approach is useful.
Key terms: binary search, sorted list, position, null, simple search, guess
1.4 A better way to search
This section explains how binary search narrows a sorted search space by half at each step, why that makes searches fast, and how a Python function tracks the remaining range.
- Middle Guess Elimination: Trace how binary search guesses the middle of the remaining range and uses a too-low or too-high result to eliminate half of the candidates.
Why it matters: Halving the possibilities is the reason binary search needs so few guesses. - Sorted Order Requirement: Explain why binary search requires a sorted list and identify a sorted example from the section.
Why it matters: Without sorted order, a middle guess would not tell you which half to rule out. - Logarithmic Search Steps: Explain the section’s worst-case step counts for binary versus simple search, including what log base 2 means here.
Why it matters: The logarithm expresses how many times halving can shrink a search space before only one candidate remains. - Search Range Tracking: Describe how the presented binary_search function tracks the part of a sorted array still to search and what it returns when it finds the item.
Why it matters: The bounds turn the idea of discarding half into a search over array positions.
Key terms: binary search, middle number, sorted order, phone book, worst case, simple search, log2 n, logarithms, binary_search, sorted array
1.5 Running time
This section compares how the maximum number of guesses grows for one-by-one search and binary search, introducing linear and logarithmic running time.
- Search running time comparison: Explain how the maximum number of guesses changes as a list grows for one-by-one search versus binary search, and name their running times.
Why it matters: Running time helps you compare algorithms when choosing an efficient approach.
Key terms: running time, linear time, logarithmic time, log time, binary search
1.6 Big O notation
This section introduces Big O notation as a way to describe algorithm speed and explains why that is useful when working with other people’s algorithms.
- Purpose of Big O notation: Explain that Big O notation tells you how fast an algorithm is and why that information is useful when you use someone else’s algorithm.
Why it matters: It gives you a way to think about the speed of algorithms you did not write.
Key terms: Big O notation, algorithm, running time
1.7 Algorithm running times grow at different rates
This section uses simple and binary search to show why an algorithm’s running-time growth matters and introduces big O notation for expressing that growth.
- Different running-time growth rates: Explain why a speed comparison on a small list cannot be assumed to hold for a much larger list. Describe how simple search and binary search diverge as list size grows.
Why it matters: A choice that looks fast enough on a small input may fail when the input grows. - Big O operation counts: Explain what big O notation expresses and give the section’s big O running times for simple search and binary search.
Why it matters: Operation growth lets you compare algorithms without treating a timing in milliseconds as a prediction for every input size.
Key terms: simple search, binary search, run time, big O notation, O(n), O(log n), operations
1.8 Visualizing different big O run times
A 16-box grid illustrates how doing one box per operation takes linear time, while doubling the number of boxes per fold takes logarithmic time.
- Linear versus logarithmic grid making: Explain why drawing 16 boxes one at a time takes 16 operations and O(n) time, while folding paper to double the number of boxes each time takes four operations and O(log n) time.
Why it matters: The grid makes the difference between linear and logarithmic growth concrete.
Key terms: operation, running time, O(n), O(log n)
1.9 Big O establishes a worst-case run time
The section explains why a fast individual search does not change simple search’s worst-case Big O run time.
- Worst-case simple search time: Explain why finding the first phone-book entry immediately does not change simple search’s O(n) run time: in the worst case, it may have to check every entry once.
Why it matters: It helps you distinguish one quick result from a guarantee about an algorithm’s worst-case run time.
Key terms: simple search, O(n), O(1), best-case scenario, worst-case scenario
1.10 Some common big O run times
Introduces five common big O run times, compares how they grow, and emphasizes that big O describes growth rather than elapsed seconds.
- Common run time ordering: State the five common big O run times in the section’s fastest-to-slowest order and identify the examples given for them.
Why it matters: This ordering gives you a quick way to compare how algorithms scale as inputs grow. - Logarithmic and linear growth: Compare the operation counts for O(log n) and O(n) when the grid grows from 16 to 1,024 boxes.
Why it matters: The grid comparison makes the difference between two growth rates concrete. - Growth rather than seconds: Explain what big O measures here and why the grid’s operation counts and seconds are only an illustration.
Why it matters: This keeps you from treating a growth-rate label as an exact stopwatch prediction.
Key terms: O(log n), O(n), O(n * log n), O(n2), O(n!), log time, operations, big O notation, number of operations, size of the input
1.11 The traveling salesperson
The section uses the traveling salesperson problem to show how checking every possible route produces factorial running time and why an approximate answer may be needed.
- Exhaustive routes and factorial growth: Explain how the described solution finds the shortest route by checking every order of the cities, adding each route’s distance, and choosing the shortest. Describe why this takes n! operations for n cities and quickly becomes impractical.
Why it matters: It gives a concrete example of why an algorithm that works for a few inputs can become unusable as the input grows. - Limits of exact route finding: Explain that the section says no fast algorithm is known for this problem and presents an approximate solution as the practical alternative, without claiming that a fast algorithm has been proved impossible.
Why it matters: It explains why the section does not simply replace the factorial method with a known fast exact one.
Key terms: traveling salesperson problem, permutations, n!, factorial time, O(n!), no fast known algorithm, approximate solution
1.12 Recap
The recap connects binary search’s growing advantage over simple search to measuring algorithm time by growth using big O notation.
- Search Speed as Lists Grow: Explain that binary search becomes much faster than simple search as the list grows, because O(log n) grows more slowly than O(n).
Why it matters: The comparison shows why running-time growth matters when choosing a search algorithm. - Algorithm Time as Growth: Describe how the recap measures algorithm time: by how running time grows, expressed in big O notation, rather than by seconds.
Why it matters: Growth describes how an algorithm’s time changes as the problem gets bigger.
Key terms: binary search, simple search, O(log n), O(n), algorithm speed, algorithm times, growth, big O notation
Where this is used later
- Which is used more, arrays or linked lists? (chapter 2) · The reader considers the choice between arrays and linked lists.
- Merge sort vs. quicksort (chapter 4) · The reader compares merge sort and quicksort.
- (chapter intro) (chapter 2) · Introduces binary search.
- (chapter intro) (chapter 5) · Binary search as a way to find an item in sorted data.
- Average case vs. worst case (chapter 4) · Distinguishing worst-case from average-case run time builds on this meaning of a worst-case bound.
- Big O notation revisited (chapter 4) · Returns to big O notation after introducing more algorithms.
- Approximation algorithms (chapter 10) · Approximation algorithms develop the alternative mentioned here.
Concepts explained in this chapter
- binary searchAn algorithm that searches a sorted list by repeatedly narrowing the search interval and returns the position of a matching element or null when no match exists.
- performanceBig O notation is a mathematical notation for describing the asymptotic growth rate of an algorithm's resource usage as input size increases.
- simple searchSimple search is a sequential search technique that checks elements one at a time until the target is found or the sequence is exhausted.
- linear time complexityLinear time describes an algorithmic running time that grows proportionally with the size of the input.
- logarithmic time complexityLogarithmic time describes an algorithmic running time that grows in proportion to the logarithm of the input size.
- sorting algorithmA sorting algorithm is an algorithm that arranges elements according to an ordering criterion.
- O(n * log n)O(n * log n) is a time-complexity bound whose operation count grows as the input size multiplied by its logarithm.
- quadratic time complexityO(n2) is a quadratic time-complexity bound whose operation count grows with the square of the input size.
- worst-case performanceThe worst-case scenario is the execution situation in which an algorithm requires its maximum runtime for inputs of a specified size.
- arrayAn array is a data structure that stores elements in indexed positions, typically in contiguous memory.
- average-case analysisAn average-case runtime is the expected execution time of an algorithm over a specified distribution of inputs of a given size.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.