Linear search, binary search, selection sort, insertion sort, input size, running time, and Big-O intuition — the tools for reasoning about how fast algorithms scale
Every day, software searches through enormous collections of data and arranges it into useful order. Search engines scan billions of web pages. Hospitals retrieve patient records in an instant. E-commerce platforms sort products by price, rating, or relevance. Music services find songs in libraries of millions of tracks. These tasks look simple from the outside, but solving them well requires careful thinking about how an algorithm works — not just whether it works.
This chapter introduces the two most fundamental algorithmic tasks in computing — searching and sorting — and the discipline of thinking carefully about efficiency: how long an algorithm takes and how much memory it uses as data grows. Students will trace algorithms step by step, compare strategies, and develop intuition for why some approaches are dramatically faster than others.
Imagine a library with ten thousand books arranged in no particular order. To find a specific title, you would have to check every book until you happened upon it. Now imagine those same books arranged alphabetically. You could open to the middle, decide whether your author comes earlier or later, keep dividing — and reach the right book in a dozen steps rather than thousands. That difference is what this chapter is about.
Searching and sorting sit at the core of almost everything computers do. Databases search records. Operating systems search directories. GPS applications search maps. Social networks search connections. Compilers search for variable names. Every one of these tasks is faster when the right algorithm is applied to the right data structure.
Understanding searching and sorting introduces a fundamental insight: two algorithms can both produce the correct answer, but one can be dramatically more efficient than the other. In computer science, correctness is necessary but not sufficient. A correct algorithm that takes a year to finish is not useful. Efficiency matters.
Organization makes searching faster. And the choice of algorithm determines how much faster. The same principle applies to sorting: the choice of strategy determines both whether you get the right answer and how long it takes to get there.
| Topic | Algorithms | Key Question |
|---|---|---|
| Searching | Linear search, Binary search | How do we find a specific item in a collection? |
| Sorting | Selection sort, Insertion sort | How do we rearrange a collection into a defined order? |
| Efficiency | Big-O intuition | How does running time grow as data grows? |
The simplest possible search strategy is also the most honest: check every item, one at a time, until you find what you are looking for — or until you have checked everything and confirmed it is not there. This approach is called linear search, sometimes also called sequential search. It is linear because the algorithm moves through the list in a straight line from beginning to end.
Suppose you have a list of student ID numbers and want to find whether 40217 appears in it:
| Situation | Steps Required |
|---|---|
| Target is the first item | 1 step |
| Target is in the middle | About n/2 steps |
| Target is the last item | n steps |
| Target is not in the list | n steps — must check everything |
Use linear search when the list is unsorted and cannot easily be sorted first, when the list is small enough that checking every item is fast, when data changes frequently making presorting impractical, or when you need to find all occurrences of an item rather than just the first.
If a list is already sorted, a much faster strategy becomes possible. Instead of checking items one by one from the beginning, you can start in the middle of the list and eliminate half the remaining candidates with a single comparison. This is binary search. Each step cuts the remaining search space in half.
[14, 22, 35, 47, 61, 73, 88, 95, 102]Binary search only works correctly on a sorted list. If the list is unsorted, eliminating half the candidates based on a comparison is not valid — the target could be anywhere. Before applying binary search, you must confirm the data is sorted or sort it first. An unsorted list may cause binary search to return -1 (not found) even when the item is present.
| Property | Linear Search | Binary Search |
|---|---|---|
| Requires sorted list? | No | Yes |
| Worst-case steps | n (all items) | about log₂(n) |
| Steps for 1,000 items | Up to 1,000 | Up to 10 |
| Steps for 1,000,000 items | Up to 1,000,000 | Up to 20 |
| Good for unsorted data? | Yes | No |
| Good for large sorted data? | No | Yes |
The number log₂(n) means "how many times you can divide n by 2 before reaching 1." For one million items, log₂(1,000,000) ≈ 20. Binary search takes at most 20 steps where linear search might take one million. That difference is enormous — and grows larger with every doubling of the dataset.
Searching is easier when data is sorted. Databases, file systems, dictionaries, phone books, spreadsheets, and libraries all depend on sorted data for efficient retrieval. Sorting means rearranging a collection of items so that they appear in a defined order — numerical, alphabetical, chronological, or by any computed property.
Why is sorting non-trivial? A computer algorithm can only compare two items at a time and then make a decision. Every sorting algorithm is built from many small two-item comparisons. The question is: in what order do you make those comparisons, and what do you do with the results? Different answers produce different algorithms with different efficiency characteristics.
Completeness: Every item in the original list appears in the sorted list.
Order: Every adjacent pair in the result satisfies the target ordering.
No duplication: Items are rearranged, not added or removed.
Selection sort is one of the simplest sorting algorithms to understand and trace. The idea is intuitive: repeatedly find the smallest remaining item and move it to its correct position. Once an item is placed, it never moves again.
[11, 25, 12, 22, 64] — position 0 is now permanent.[11, 12, 25, 22, 64] — positions 0–1 permanent.[11, 12, 22, 25, 64] — positions 0–2 permanent.[11, 12, 22, 25, 64][11, 12, 22, 25, 64]| Pass | List State | Action |
|---|---|---|
| Start | [64, 25, 12, 22, 11] | Unsorted |
| 1 | [11, 25, 12, 22, 64] | Swapped 11 and 64 |
| 2 | [11, 12, 25, 22, 64] | Swapped 12 and 25 |
| 3 | [11, 12, 22, 25, 64] | Swapped 22 and 25 |
| 4 | [11, 12, 22, 25, 64] | No swap needed |
| Done | [11, 12, 22, 25, 64] | Sorted ✓ |
Selection sort always makes the same number of comparisons regardless of how the data is arranged. Even on an already-sorted list, it scans every remaining item to confirm the minimum. This predictability is both its strength (guaranteed behavior) and its weakness (no shortcut for easy inputs).
Insertion sort works differently. Instead of finding the minimum on each pass, it takes one item at a time from the unsorted portion and inserts it into the correct position within the already-sorted portion. Think of the way many people sort a hand of playing cards: you pick up one card at a time and slide it into the right position among the cards you are already holding.
[5]. Unsorted: [2, 8, 1, 9, 3][2, 5, 8, 1, 9, 3][2, 5, 8, 1, 9, 3][1, 2, 5, 8, 9, 3][1, 2, 5, 8, 9, 3][1, 2, 3, 5, 8, 9]If the list is already sorted, the inner while loop never executes. Each new item is larger than everything already sorted, so it just gets appended at the end. In that case, insertion sort completes in only n comparisons — much faster than selection sort on the same data. This makes insertion sort ideal for lists that are already sorted or nearly sorted, and for online settings where items arrive one at a time.
Consider a sorted list of one million items. With linear search, the worst case requires checking all one million items. With binary search, the worst case requires at most 20 comparisons, since 2²⁰ = 1,048,576. The table below makes this concrete.
| Items in List | Linear Search (worst case) | Binary Search (worst case) |
|---|---|---|
| 10 | 10 comparisons | 4 comparisons |
| 100 | 100 comparisons | 7 comparisons |
| 1,000 | 1,000 comparisons | 10 comparisons |
| 1,000,000 | 1,000,000 comparisons | 20 comparisons |
| 1,000,000,000 | 1,000,000,000 comparisons | 30 comparisons |
| Situation | Selection Sort | Insertion Sort |
|---|---|---|
| Already sorted | Still does all comparisons | Very fast — O(n) comparisons |
| Reverse sorted | Full work | Full work — worst case |
| Random order | Full work | About half of worst case |
Selection sort and insertion sort are both called O(n²) algorithms. For a list of 10,000 items, that means roughly 100,000,000 comparisons in the worst case. More efficient algorithms — mergesort, quicksort, heapsort — can sort n items in O(n log n) time. Those are covered in later courses. For now, the key insight is: algorithm design choices have profound consequences as data scales up.
One of the most important ideas in algorithm analysis is that the relationship between input size and running time determines how well an algorithm scales. Input size is usually measured as the number of items being processed — conventionally written as n. Running time is the number of basic operations the algorithm performs.
The critical question is not "how fast is this algorithm on my current data?" but rather: how does running time grow as n grows?
| n | Algorithm A — n steps | Algorithm B — n² steps | Algorithm C — 2ⁿ steps |
|---|---|---|---|
| 100 | 0.001 sec | 0.001 sec | Vastly longer than universe age |
| 1,000 | 0.01 sec | 0.1 sec | Impossible in practice |
| 10,000 | 0.1 sec | 10 sec | Impossible in practice |
| 1,000,000 | 10 sec | 11.6 days | Impossible in practice |
Algorithm C with 2ⁿ steps becomes completely impractical even for modest input sizes. This illustrates why growth rate dominates over constant factors: an algorithm that does 100·n operations will eventually outperform one that does n² operations, because n² grows much faster than 100n as n increases. Specifically, 100n < n² whenever n > 100.
| Category | Description | Example |
|---|---|---|
| Best case | Most favorable input — fewest operations | Linear search finds target at position 0 |
| Worst case | Most unfavorable input — most operations | Linear search: target absent, checks all n items |
| Average case | Expected behavior across typical inputs | Linear search: target at middle on average |
Worst-case analysis provides an upper bound guarantee. You can promise a user that binary search will finish in at most 20 steps for a million-item list, regardless of where the target is. That guarantee is impossible to make from average case alone. In critical systems — databases, medical records, real-time applications — knowing the ceiling matters as much as knowing the average.
Computer scientists use a notation called Big-O to describe the growth rate of an algorithm's running time in a standardized, precise way. The notation O(f(n)) means: as n grows large, the algorithm's running time grows no faster than a constant multiple of f(n). The function inside the notation captures the dominant growth behavior, ignoring constants and smaller terms.
| Notation | Name | What It Means | Examples |
|---|---|---|---|
O(1) | Constant | Time does not change with input size | Array index lookup, hash table lookup |
O(log n) | Logarithmic | Time grows very slowly — doubles when input squares | Binary search |
O(n) | Linear | Time grows in proportion to input size | Linear search, scanning a list |
O(n log n) | Linearithmic | Slightly worse than linear — efficient sorting | Mergesort, Timsort |
O(n²) | Quadratic | Time grows as the square of input size | Selection sort, insertion sort (worst) |
O(2ⁿ) | Exponential | Doubles for every additional item — quickly infeasible | Brute-force combinatorial problems |
| Algorithm | Big-O | Notes |
|---|---|---|
| Linear search | O(n) | Must check up to n items in the worst case |
| Binary search | O(log n) | Halves the search space each step; requires sorted input |
| Selection sort | O(n²) | Two nested loops over n items; always the same work |
| Insertion sort | O(n²) worst, O(n) best | Best case on already-sorted data; depends heavily on input |
Big-O does not tell you exactly how many seconds an algorithm will take. It tells you how running time grows relative to input size. Two O(n) algorithms might differ by a factor of 10 in raw speed. Big-O ignores those constants. This is why algorithm analysis and hardware optimization are complementary, not interchangeable: a faster computer helps every algorithm, but a better algorithm helps even more as data grows.
In real software, the choice of algorithm is never made in isolation. It is made in the context of a system with real constraints: How much data will be processed? How often will it be searched versus updated? How much memory is available? How fast must results appear? Is the data already partially sorted? These questions reveal that efficiency is not just about comparing one algorithm to another in the abstract — it is about matching algorithms to the reality of the problem.
If a dataset is searched thousands of times but changes rarely, it is worth the cost of sorting it once in order to benefit from binary search on every subsequent lookup. A dictionary is built and sorted once; you then look up words millions of times, and every lookup is fast because the dictionary is sorted. But if data changes constantly, maintaining sorted order becomes expensive, and different data structures and indexing strategies are used instead.
Selection sort and insertion sort both sort the list in-place, using only a small constant amount of extra memory. Mergesort, a more efficient O(n log n) algorithm, requires additional memory proportional to the list size for temporary storage. It is faster in time but more expensive in memory. This tradeoff — trading memory for time, or time for memory — is fundamental in systems design.
Python's built-in sorted() and list.sort() use an algorithm called Timsort, which detects already-sorted runs in data and uses insertion sort for small segments while using merge sort for large ones. It takes advantage of insertion sort's best-case strength and mergesort's overall efficiency. Understanding the principles behind sorting algorithms helps you recognize why a standard library function is both safe and fast to trust.
Algorithm efficiency is not just a performance concern — it can become a security concern. Some servers have been attacked using algorithmic complexity attacks: the attacker sends inputs designed to trigger the worst-case behavior of a vulnerable algorithm, consuming so much CPU time that the server becomes unresponsive. Choosing algorithms whose worst case is controlled and predictable is one element of robust, secure system design.
The study of searching and sorting is, at a deeper level, the study of a foundational question in computer science: how do we design step-by-step procedures that solve problems correctly and scale gracefully? Every topic that follows — data structures, databases, operating systems, networks, machine learning — involves algorithms that must work on real data at real scale. The habits of thought in this chapter are habits you will use throughout your computing work.
| Step | Index | Value | Match? |
|---|---|---|---|
| 1 | 0 | 45 | No |
| 2 | 1 | 19 | No |
| 3 | 2 | 73 | Yes — return 2 ✓ |
| Step | low | high | mid | list[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 41 | 50 > 41 → low = 5 |
| 2 | 5 | 8 | 6 | 68 | 50 < 68 → high = 5 |
| 3 | 5 | 5 | 5 | 55 | 50 < 55 → high = 4 |
| 4 | low (5) > high (4) → Return -1 (not found) ✓ | ||||
| Pass | Minimum Found | Action | Result |
|---|---|---|---|
| 1 | 10 at index 1 | Swap 29 and 10 | [10, 29, 14, 37, 13] |
| 2 | 13 at index 4 | Swap 29 and 13 | [10, 13, 14, 37, 29] |
| 3 | 14 at index 2 | No swap needed | [10, 13, 14, 37, 29] |
| 4 | 29 at index 4 | Swap 37 and 29 | [10, 13, 14, 29, 37] |
| Done | [10, 13, 14, 29, 37] — Sorted ✓ | ||
Fill in the correct term for each statement.
[12, 44, 71, 55, 30, 82, 19]. Show each step. How many comparisons does it take?[5, 12, 20, 30, 45, 60, 75, 88, 96]. Show each step with low, high, and mid values.[8, 3, 7, 1, 5]. Show the list after each complete pass.[4, 6, 2, 9, 1]. Show the list after each item is inserted into the sorted region.[10, 50, 20, 40, 30] to find the value 40. What must happen first?[1, 2, 3, 4, 5] (already sorted) versus [5, 4, 3, 2, 1] (reverse sorted). For each combination, describe qualitatively how much work is done. Which algorithm benefits more from the already-sorted input?Identify the bug. What happens when low and high point to the same index? What should the condition be?
The code runs without crashing but sometimes produces incorrect results. When i reaches the last position, what does the inner loop search? What should the outer range be?
What should list[j] be set to during the shifting step? Write the corrected line.
The student is confused because 40 is clearly present. Explain exactly what went wrong. What precondition was violated? What should the student have done first?
[92, 17, 44, 63, 5, 38]. How many comparisons?[3, 14, 27, 38, 51, 66, 77, 89, 95]. Show all steps with low, high, mid.[35, 8, 22, 4, 17]. Show the list after every pass.[3, 7, 1, 5, 2]. Show the list after each insertion step.while low < high instead of while low <= high. Describe a case where this causes the algorithm to miss the target.Chapter 13 introduces abstraction, models, and simulation — one of the most powerful ideas in computer science and in science generally. You have already encountered abstraction in this chapter: pseudocode abstracts away specific programming language details; Big-O notation abstracts away constant factors to focus on growth rate; a "sorted list" abstracts away what the items are and focuses only on their relative order.
Chapter 13 makes this concept explicit. Students will learn how computer scientists build simplified models of complex systems, what assumptions those models rely on, and how simulations allow us to study systems that would be too expensive, too dangerous, or too slow to study directly. Abstraction and modeling appear in every area of computing — databases model organizations, networks model communication, machine learning models data patterns, operating systems model physical hardware.