- Home
- /
- CS Thinking
- /
- Concept Map
- /
- Algorithms
Algorithms Concepts
9 concepts · Grades 6-8, 9-12 · 9 prerequisite connections
Concept Dependency Graph
Concepts flow left to right, from foundational to advanced. Hover to highlight connections. Click any concept to learn more.
Connected Families
Algorithms concepts have 11 connections to other families.
How Algorithms Connects to Other Topics
Algorithms concepts build on and feed into concepts across other families. Understanding these connections helps you plan what to study before and after.
Builds on
All Algorithms Concepts
Recursion
A technique where a function calls itself to solve progressively smaller instances of the same problem. Every recursive solution has two parts: a base case that stops the recursion, and a recursive case that breaks the problem into a smaller version of itself.
"Looking up a word can be recursive: if the definition uses a word you do not know, you look that word up first, then come back to where you were. You stop at a definition made only of words you know, the base case. A dictionary that defines 'big' as 'large' and 'large' as 'big' is infinite recursion: the lookups never end."
Why it matters: Some problems are awkward with loops but short with recursion: listing every file in nested folders, exploring a maze, drawing a fractal, sorting a list by sorting its halves. Recursion lets you solve one level and trust the same code to handle the rest. Get the base case wrong and the calls never stop; the program crashes with a stack overflow.
Algorithm Efficiency
Big-O notation describes the asymptotic growth of an algorithm's cost as input size increases — most often applied to worst-case running time or memory, expressed as $O(n)$, $O(n^2)$, $O(\log n)$, etc.
"Big-O compares ways of running a party. Handing each guest an invitation takes time in proportion to the guest list: $O(n)$. Having every guest shake hands with every other guest grows with the square: $O(n^2)$. Big-O asks how the job grows as the party gets bigger, not how fast one particular helper walks."
Why it matters: Suppose a method takes 1 second on 1,000 items. On 1,000,000 items it takes about 2 seconds if it is $O(\log n)$, about 17 minutes if it is $O(n)$, and about 11.6 days if it is $O(n^2)$. A test run on small data cannot tell these apart, but the shape of the code can. Without that analysis, programs pass every small test and then freeze on real data.
Searching
The process of locating a specific item or value within a collection of data using a systematic strategy. The two fundamental approaches are linear search (check every element one by one) and binary search (repeatedly halve the search space in sorted data).
"Searching a sorted list is the game 'guess my number from 1 to 100' with 'higher' or 'lower' hints: guessing the middle every time finds any number in 7 guesses or fewer. Take the hints away and the only safe plan is guessing 1, 2, 3 and so on, which is linear search."
Why it matters: Search runs constantly behind every app: logging in looks up your username, a spell-checker looks up each word, a store finds a product's price. The strategy decides whether that takes 20 steps or a million. Choosing wrong also breaks things: binary search on unsorted data reports 'not found' for items that are there, and a search with no not-found rule can run past the end of the list.
Sorting
Rearranging items in a collection into a defined order, such as smallest to largest or alphabetical. Sorting is one of the most studied problems in computer science, with algorithms ranging from simple (bubble sort, $O(n^2)$) to efficient (merge sort, $O(n \log n)$).
"Lining up a class by height for a photo is sorting. Neighbors can keep swapping until no pair is out of order (bubble sort), or the class can split in two, line up each half, and merge the two lines by sending forward the shorter front person each time (merge sort). A computer cannot see the whole line at once; it compares two people at a time."
Why it matters: Sorted data makes other jobs cheap: the median, duplicates (they end up side by side), merging two lists and binary search all rely on order. For 100,000 items bubble sort needs about 5 billion comparisons while merge sort needs about 1.7 million, the difference between minutes and an instant. And a sort with the wrong key or direction quietly produces a list that looks ordered but answers the wrong question.
Binary Search
An efficient algorithm for finding a target value in a sorted list by repeatedly halving the search range. At each step, compare the target to the middle element: if equal, the search is done; if smaller, search the left half; if larger, search the right half.
"Binary search is how you find page 412 in a thick book: open near the middle, see whether the page number there is too high or too low, and keep only the half that must contain 412. It works because page numbers are in order; if the pages were shuffled, the number you opened to would tell you nothing."
Why it matters: Binary search is why looking something up in a huge sorted index feels instant: doubling the data adds just one comparison. It is also famously easy to get subtly wrong. Writing high = mid instead of mid − 1 can loop forever, a missing low ≤ high check runs off the list, and on unsorted data it reports 'not found' for values that are there.
Linear Search
A search algorithm that checks each element in a list one by one, starting from the first, until the target is found or the entire list has been examined. It is the simplest search algorithm and works on both sorted and unsorted data.
"Linear search is reading down a printed sign-up sheet to find a name: start at the top, read each name, stop when you see it. You never skip ahead, because the sheet gives no clue where the name might be. Reaching the bottom without seeing it is the only way to be sure the name is not there."
Why it matters: Linear search is the method you can always fall back on: unsorted lists, lists that change constantly, searches by any property, such as the first student taller than 160 cm. Knowing its cost tells you when it stops being good enough: a million unsorted records can take a million comparisons. And a forgotten not-found case returns a wrong answer or crashes.
Merge Sort
A divide-and-conquer sorting algorithm that splits a list in half, recursively sorts each half, then merges the two sorted halves back together in order. The key insight is that merging two already-sorted lists into one sorted list is efficient and straightforward.
"Merge sort is like sorting a tall stack of exam papers with a group of friends: keep halving the stack and passing halves on until each person holds a single paper, which is already sorted. Then pairs of people combine their piles by repeatedly taking the lower-scoring of the two top papers, until one sorted stack is left. A program does the passing on with recursion."
Why it matters: Merge sort turns sorting from $O(n^2)$ into $O(n \log n)$, and it guarantees that speed on every input, sorted, reversed or random. For a million items that is about 20 million comparisons instead of about 500 billion. It is stable, so it suits sorting records by several fields, and its merge step is how databases sort files too big for memory. The price is memory: merging needs a second array as large as the input.
Bubble Sort
A simple sorting algorithm that repeatedly walks through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. This process repeats until no more swaps are needed, meaning the list is fully sorted.
"Bubble sort is like tidying books by height on a shelf when you may only swap two neighboring books. Walking left to right, you swap whenever a taller book stands left of a shorter one, so the tallest book is carried to the right end in a single sweep. A short book stuck at the far right moves only one place per sweep, which is why the method is slow."
Why it matters: Bubble sort is easy to trace by hand, which makes it the clearest place to see what a sorting algorithm promises: after pass $k$, the $k$ largest values are in their final places. Its cost is the warning: 10 items need at most 45 comparisons, but 10,000 items need up to about 50 million. The early-exit check matters too, because it turns an already sorted list into a one-pass job.
Divide and Conquer
Divide and conquer is an algorithmic strategy that splits a problem into smaller subproblems of the same kind, solves those smaller problems, and then combines their solutions into one final answer. It is a structured form of decomposition often paired with recursion.
"Counting a national vote works like divide and conquer: each town counts its own ballots, each region adds up its towns' totals, and the country adds up its regions. Every level does the same job, counting, on a smaller piece, and the totals combine on the way up. All the towns can count at once, the same reason these algorithms split well across processors."
Why it matters: Divide and conquer is behind many of the fastest known algorithms: merge sort's $O(n \log n)$, fast multiplication of huge numbers, and the Fast Fourier Transform used in audio and image processing. Its parts are independent, so the work splits naturally across many processors. The recurrence $T(n) = aT(n/b) + f(n)$ predicts the cost before you write code, and it shows when a lopsided split or an expensive combine step wipes out the gain.