The Role of Algorithms in Computing

By the end of this lesson you will be able to define what an algorithm actually is, prove one is correct, write and trace your very first two algorithms (linear search and binary search), explain — with a worked race — why a better algorithm beats faster hardware, and read the pseudocode style used for the rest of this track.

What is an algorithm?

Think of an algorithm like a recipe. A recipe lists a finite number of precise steps ("chop 2 onions", "heat oil to 180°C") that turn raw ingredients (the input) into a finished dish (the output). Two different cooks following the exact same recipe on the same ingredients must end up with the same dish — that's what makes it a reliable recipe rather than vague improvisation. An algorithm is the same idea for a computer: a finite, precise sequence of steps that turns an input into an output.

In short: an algorithm is a precise, finite procedure that takes some input and, step by step, produces some output. You can also think of it as a tool for solving a computational problem: the problem states the input-to-output relationship you want in general ("given a list of numbers, produce the same numbers in ascending order"); an algorithm is one specific procedure for achieving it.

Two words matter enormously here and are easy to blur together:

A problem is the general question: "sort any sequence of numbers into non-decreasing order."
A problem instance is one specific input to that problem: the particular list [47, 12, 85, 30, 12, 66] is an instance of the sorting problem. The instance is what you actually hand the algorithm; the problem is the promise the algorithm keeps for every possible instance.

An algorithm is correct if, for every input instance, it halts with the correct output. A correct algorithm solves the given computational problem. An incorrect algorithm might still be useful, though, if you can control or understand its error rate — you'll meet exactly this trade-off with the Miller–Rabin primality test later in this track (number theory), which is allowed to be wrong with tiny, tunable probability in exchange for being far faster than any known algorithm that is guaranteed always correct.

A beginner trap: assuming "gives the right answer on the examples I tried" is the same as "correct." Correctness is a claim about every instance, including ones nobody tried by hand — an empty input, a single element, all-equal elements, already-sorted input, the largest input size you'll ever realistically see. Every algorithm test suite you write in this course (and in the verify/ files behind every lesson) exists precisely to probe those edges, not just the friendly middle case.

Here is that same trap made concrete: two searches, run on the exact same unsorted array, where one is genuinely correct and the other only looks correct — right up until you hand it an input that breaks a hidden assumption it never told you about:

Input size → what is feasible: both versions are Θ(n): n = 10⁶ elements is 10⁶ steps (~10 ms). The point is not speed but that BUGGY is wrong on unsorted input of every size.

Algorithm = a finite, precise recipe from input to output. Instance = one concrete input. Correct = halts with the right output on every instance.

Problems algorithms solve

Sorting is this track's running example because it is simple to state yet rich enough to illustrate almost every idea — but algorithms are the workhorse behind problems far beyond sorting. A quick preview of problems you'll meet later in this track, with why the "obvious" approach usually isn't good enough:

Problem	One naive approach	Why that's not good enough	Where in this track
Shortest path between two cities on a road map	Try every possible route	The number of routes explodes combinatorially as the map grows	Shortest paths (BFS, Dijkstra, Bellman-Ford)
Longest common subsequence of two DNA strings	Check every subsequence of the shorter string	A string of length m has 2^m subsequences	Dynamic programming
Order tasks so every prerequisite comes first	Try every permutation of the tasks	n tasks have n! orderings	Graph search (topological sort)
Smallest fence enclosing a set of points (convex hull)	Test every pair/triple of points for validity	Grows too fast to use on large point sets	Computational geometry
Multiply two polynomials fast	Multiply every pair of coefficients	Θ(n²) naive vs Θ(n lg n) with the FFT	The FFT
Allocate a factory's resources to maximize profit	Try every allocation	Even a modest number of resources yields an unmanageable number of allocations	Linear programming
Send a secret message only the intended reader can read	—	Needs a mathematically hard problem to build security on	Number theory (RSA)

You'll notice a pattern already: in every row, the naive approach is correct — it will eventually produce the right answer — but its running time grows so explosively with the input size that it is useless in practice for anything but tiny instances. The rest of this track is largely about designing algorithms whose running time grows far more slowly than "try everything."

Here is how fast "try everything" explodes, as code: the number of candidate subsequences (2^m), orderings (n!), grid routes (C(2n, n)) and coefficient products (n·m) from the table above, and what they cost at 10⁸ simple steps per second:

Input size → what is feasible: brute-force over 2^m subsequences is fine for m ≤ 25 (3.4·10⁷ candidates, well under a second) but m = 60 needs ≈ 365 years; n! orderings are fine for n ≤ 10 (3.6·10⁶) and hopeless at n = 20 (2.4·10¹⁸); naive polynomial multiplication (n·m) is fine for n, m ≤ 10⁴ (10⁸ products) — beyond that use the FFT.

Your first two algorithms: linear & binary search

Imagine a shelf of numbered lockers. Linear search is checking every locker from left to right until you find the one you want — slow, but works even if the lockers are in random order. Binary search is the "guess the number between 1 and 100" game: you're only allowed to ask "is it higher or lower?", so you always guess the middle of the remaining range, which eliminates half the possibilities with every guess. Binary search's trick only works because the lockers (or the range) are already sorted — you couldn't play "higher or lower" on a shuffled deck.

Pseudocode conventions used here (explained fully in the last section of this page): arrays are 0-indexed exactly like Dart (the first element is a[0]), indentation shows nesting instead of braces, ← means "store into", and null stands for "no value".

linearSearch(a, v) scans the array one element at a time and returns the index of the first element equal to v, or null if it never finds one:

Input size → what is feasible: Θ(n) per query: n = 10⁶ → 10⁶ comparisons (~10 ms) is fine for ~100 queries (10⁸ steps ≈ 1 s); n = 10⁶ with 10⁵ queries = 10¹¹ steps is far too slow → sort once and use binary search, or build a hash set.

Linear search makes no assumption about order, so it always works — but in the worst case (target missing, or at the very end) it inspects all n elements: Θ(n).

binarySearch(a, v) requires a to already be sorted ascending. It keeps a shrinking window [low, high], always checks the middle element, and throws away the half of the window that can't possibly contain v:

Input size → what is feasible: Θ(lg n) per query: n = 10⁷ sorted items → at most ⌊lg 10⁷⌋ + 1 = 24 probes, so 10⁶ queries cost ~2.4·10⁷ steps (instant) where linear search would cost 10¹³. Sorting first is Θ(n lg n) once.

Running binary search on an unsorted array doesn't just give a slower answer — it can give a wrong answer, silently. The whole algorithm depends on the invariant "everything left of low is too small, everything right of high is too big," which only holds because the array is sorted. That's why every binary-search interview question starts by confirming the array is sorted.

Why is binary search so much faster? Each comparison throws away half of the remaining candidates, so after k comparisons only n/2^k candidates remain. The search ends once that count reaches 1, i.e. when 2^k ≥ n, so k ≈ lg n. That's why binary search runs in Θ(lg n) time — we'll make "Θ" and "lg" precise in the growth-of-functions lesson, but informally: doubling the array size costs binary search only one more comparison, while it costs linear search a whole extra pass.

The same statement in code — the number of candidates left after k probes is ⌊n / 2^k⌋, the worst case ends after ⌊lg n⌋ + 1 probes, and doubling n adds exactly one probe:

Data structures — a first look

If an algorithm is the recipe, a data structure is how the ingredients are organized on the counter before you start cooking. The same ingredients, arranged well (everything within reach, labelled, grouped by use) make the recipe faster and less error-prone; arranged badly, the same recipe takes forever, even though the steps didn't change.

A data structure is a way to store and organize data so it can be used efficiently — which operations are fast (and which are slow) depends entirely on the structure you pick, not just on the algorithm. This track has a whole stretch of lessons dedicated to exactly this: stacks, queues, linked lists, hash tables, search trees, and more, each optimized for a different pattern of use. No single "best" data structure exists — choosing one is itself part of algorithm design, and you'll see the same problem solved very differently depending on which structure backs it.

As code: the same question "is x present?" answered by three structures — an unsorted list (scan), a sorted array (binary search) and a hash set — with the number of comparisons counted:

Input size → what is feasible: for 10³ items and 10³ lookups the scan costs ~6·10⁵ comparisons and binary search ~10⁴; at 10⁶ items and 10⁶ lookups the scan is ~10¹² steps (hours) and the other two are ~2·10⁷ / 10⁶ (instant).

Hard problems — an NP teaser

Not every problem has a known efficient algorithm. A famous example is the traveling-salesman problem: given a set of cities and the distances between every pair, find the shortest possible route that visits every city exactly once and returns to the start. Nobody has ever found an algorithm that solves it efficiently for large inputs — but nobody has proven that no efficient algorithm can exist, either. Problems in this shadowy middle ground are called NP-complete: if any single one of them were solved efficiently, it's provable that all of them would be too, because they can all be translated into each other. That single fact is what makes the search for an efficient algorithm (or a proof that none exists) one of the biggest open problems in computer science.

The practical takeaway for now: when you can't find an efficient exact algorithm and a proof of NP-completeness confirms you're not just missing something obvious, the sensible move is often an approximation algorithm — one that runs fast and provably gets close to the best possible answer, even if it can't guarantee the exact optimum.

Brute force on a tiny instance, in code — fix city 0 as the start and try every ordering of the other n − 1 cities, so (n − 1)! tours (5 cities → 24, 20 cities → 19! ≈ 1.2·10¹⁷):

Input size → what is feasible: n ≤ 10 cities (9! = 362,880 tours) is instant; n = 15 is 14! ≈ 8.7·10¹⁰ tours (~15 minutes at 10⁸/s); n = 20 is ~38 years → use dynamic programming (O(2ⁿn²)) up to n ≈ 20 or an approximation algorithm beyond.

Algorithms as a technology

Imagine two delivery companies. Company A has a fleet of very fast trucks but plans routes by trying random orders. Company B has much slower, older trucks, but plans routes with real logistics software. As the number of stops grows, Company B's smarter routing beats Company A's faster trucks — and the gap only widens the more stops you add. Hardware speed is a constant-factor advantage; a better algorithm's advantage grows with the input, and growth always wins eventually.

Here is a computation you can verify yourself. Take two computers sorting the same 10⁷ numbers:

Computer A: 10⁹ instructions/second, running insertion sort, which needs roughly 3n² instructions for an input of size n.
Computer B: 10⁶ instructions/second (1000× slower), running merge sort, which needs roughly 40 n lg n instructions.

Play with the input size below and watch the two running times race:

At n = 10⁷: computer A takes 3·(10⁷)² / 10⁹ = 300,000 seconds (about 3.5 days). Computer B takes 40·10⁷·lg(10⁷) / 10⁶ ≈ 9,301 seconds (about 2.6 hours) — computer B is over 32× faster despite hardware that is 1000× slower. At n = 10⁸ the gap widens further: about 347 days for A versus about 1.2 days for B.

The same formulas as code (3n²/10⁹ seconds and 40 n lg n/10⁶ seconds), checked against the numbers above, plus the n beyond which the slower machine wins for good:

Input size → what is feasible: the formulas are O(1) to evaluate for any n up to 10⁹; the crossover scan is 2·10⁶ iterations. Practical reading: below n ≈ 2.4·10⁵ the fast machine running insertion sort still wins; at n = 10⁷ the slow machine running merge sort is 32× faster.

This doesn't mean hardware never matters — for small enough n, the faster machine's smaller constant factor can still win (insertion sort's simplicity makes it genuinely the better choice for small arrays, which is why real sorting libraries switch to it below a size threshold). It means the growth rate of an algorithm's running time — how fast the work scales as n grows — eventually dominates any fixed hardware speed-up, once n is large enough. Two small calculations pin down exactly where "eventually" kicks in — first, where 5n² stops beating 60 n lg n:

As code: that crossover, a second one (the smallest n where 2ⁿ overtakes 50n²), plus the algebra step (divide 5n² < 60 n lg n by 5n to get n < 12 lg n) checked for every n:

Input size → what is feasible: both are bounded scans of at most 1000 / 200 iterations — instant; the scan limit is safe because n > 12 lg n for every n ≥ 75 and 2ⁿ outgrows 50n² for every n ≥ 14.

A common beginner instinct is "just get faster hardware" or "the constants don't matter, only the shape does." Both are half-true and both cause real mistakes: constants absolutely matter for small n (that's why insertion sort still ships inside production sort routines for small subarrays), but for large n, only the growth rate — the exponent or the presence of a log factor — decides who wins, no matter how large you make the constant multiplier on the "worse" side.

How big a problem fits in a time budget?

Now flip the previous question around: instead of "how long does size n take?", ask "for a fixed time budget, how large an n can I handle?" — for each order of growth. To keep the arithmetic simple we use a plain machine model: one step of the algorithm is one instruction, and the machine runs a fixed number of instructions per second. The animation below defaults to a budget of 1 second on a machine doing 10⁸ instructions/second (capacity = 10⁸ instructions); try it, then change either number to see the picture shift on faster or slower hardware:

As code, one generic function answers every row (double n until the cost no longer fits, then binary-search n itself), and two closed forms cover the huge Θ(√n) and Θ(lg n) rows:

Input size → what is feasible: maxNFor does ≈ 2·lg(answer) cost evaluations — ≤ ~120 even for budgets up to 10¹⁸ instructions — whereas scanning n = 1, 2, 3, … would take 10¹² steps for the Θ(n) row at 1 s.

Notice how differently the growth classes behave for the same budget: at the default budget (1 second at 10⁸ instructions/second), the largest solvable n is a full 100,000,000 for Θ(n) and 4,523,071 for Θ(n lg n), but only 10,000 for Θ(n²), 464 for Θ(n³), 26 for Θ(2ⁿ), and a mere 11 for Θ(n!) — that one table row is the entire reason brute-force permutation search (try every possible ordering) is unusable for all but toy-sized inputs, and why whole families of techniques like dynamic programming, greedy algorithms, and approximation exist: they're strategies for avoiding factorial- and exponential-time algorithms whenever a problem's structure allows it.

How to read the pseudocode in this track

Every algorithm lesson from here on shows plain pseudocode before showing Dart. Its names match the Dart functions. A few conventions, once memorized, make every future lesson easier to read:

Convention	Meaning
Arrays are 0-indexed	`a[0]` is the first element and `a[n − 1]` (where n is `a.length`) is the last — exactly like Dart's `List`, so pseudocode and Dart use the same indices with no shifting.
Indentation = blocks	No `{ }` or `begin/end` — nesting is shown purely by how far a line is indented, like Python; `for`, `while`, `if` and `else` lines end with a colon, and `←` means "store into" (`x ← 5`).
Loop counter keeps its final value	After `for i from 0 to n − 1:` finishes normally, `i` equals n (the first value that failed the test) — not `n − 1`. This matters for reasoning about loop invariants after the loop ends.
`to` / `down to` / `step`	`for i from n − 1 down to 0:` counts backward; `for i from 0 to n − 1 step 2:` steps by 2.
Variables are local by default	A variable used in a procedure is local to it unless explicitly stated otherwise (rare, and always called out).
Objects and arrays are passed by pointer	Parameters are passed by value, but for a compound object (array, list, tree node) the "value" being copied is a reference to it — matching exactly how Dart passes `List` and objects (see the closures/functions lesson, D07).
`null`	"No value" — is exactly Dart's `null`, which is why this lesson's Dart functions return `int?` instead of a magic sentinel like `-1`.
`error "message"`	Signals a precondition failure — translates to Dart throwing an exception (e.g. `ArgumentError`).
Multiple return values	Pseudocode may return several values at once where convenient; Dart 3 does the same with records, e.g. `(int, int)` — you'll see this below in `findMinMax`.

Every row of that table, as code:

Input size → what is feasible: all of these are O(1) or a single pass; the only trap is remembering that a loop which finishes normally leaves its counter at n, not n − 1.

You'll also see Θ, O, and Ω starting in the very next lessons, formalized fully in the growth-of-functions lesson (C03). Informally, for now: Θ(g(n)) means "grows at the same rate as g(n), once n is large enough — not faster, not slower, ignoring constant multipliers and lower-order terms." So Θ(n²) means "roughly proportional to n², for large n" — 3n² + 100n is Θ(n²) because once n is big, the 3n² term completely dominates the 100n term and the constant 3 doesn't change the shape of the growth. Saying an algorithm "is Θ(n²)" is a promise about its growth shape, not a promise about the exact number of steps on any one input.

The Θ claim above, as code (f(n) = 3n² + 100n, sandwiched between 3n² and 4n² from n₀ = 100 on):

Where to go from here: math foundations for reading running-time formulas precisely live in M01 (logs, powers, summations) and M02 (counting & probability, needed for the randomized algorithms later on). If any Dart syntax here felt unfamiliar, the Dart track (starting at D00) builds it up from how a computer runs code at all. The very next lesson, C02, formalizes insertion sort and merge sort — the two algorithms you just raced above — with a full loop-invariant correctness proof.

Quiz

Interview questions

Cheat sheet

Algorithm	Best	Average	Worst	Space	Requires sorted input?	When to use
Linear search	Θ(1)	Θ(n)	Θ(n)	Θ(1)	No	Unsorted data, or a one-off search not worth sorting first
Binary search	Θ(1)	Θ(lg n)	Θ(lg n)	Θ(1) iterative / Θ(lg n) recursive (call stack)	Yes	Sorted (or sortable-once, searched-many-times) data
Ternary search	Θ(1)	Θ(lg n)	Θ(lg n)	Θ(1)	Yes	Same order of growth as binary search but more comparisons per step — rarely a real improvement (see Q22)

Ternary search (the cheat-sheet row above), as code: it finds the same index, but its comparison count model 2·log₃ n exceeds binary's lg n by a factor 2/lg 3 ≈ 1.26:

Input size → what is feasible: Θ(lg n) like binary search: n = 10⁷ → ~30 comparisons versus ~24; never preferable to binary search.

Order-of-growth cheat sheet (slowest-growing to fastest-growing, so a smaller class can always handle a bigger n for the same time budget): lg n < √n < n < n lg n < n² < n³ < 2ⁿ < n! — this is exactly the row order used in the time-budget animation above, and the ordering the growth-of-functions lesson (C03) proves rigorously.