Algorithms: clear steps for solving problems

A visual field guide to designing, proving, analyzing, and choosing algorithms—from the first loop to graphs and dynamic programming.

Start with the idea

An algorithm is a clear, ordered set of steps for completing a task or solving a problem. A recipe is a simple everyday example: it lists ingredients and tells you what to do with them, in order.

In computing, an algorithm takes some input, works on it, and produces an output. For example, an algorithm can take a list of numbers as input and produce the largest number as output.

• Input: information the algorithm is given.
• Output: the answer or result it produces.
• Step: one instruction in the plan.
• State: the information the algorithm keeps track of while it works.

An algorithm is the plan; a program is its expression in code

An algorithm describes what steps solve the problem. A program writes those steps in a programming language such as C, Python, or JavaScript so a computer can run them. You can plan and check the steps before choosing a language.

A useful first plan answers four questions:

1. What information will the algorithm receive?
2. What result should it produce?
3. What steps transform the input into that result?
4. What special cases could make the plan fail, such as an empty list?

Worked example: find the largest number

Suppose the input is the list [4, 9, 2, 7]. We want the largest value, which is 9. We will scan the list from left to right and remember the largest value seen so far.

Initialize means to give a variable its first value before using it. Start by setting largest to the first number in the list. This gives us a real list value to compare against; we do not need to guess a starting number that might be too small.

if the list is empty:
    report that there is no largest number
otherwise:
    largest = the first number in the list
    for each remaining number:
        if that number is greater than largest:
            largest = that number
    return largest

This is pseudocode: a readable outline of instructions, not code that a particular programming language can run. Read it one step at a time:

1. Check for an empty list before trying to read its first number.
2. Initialize largest to 4, the first number.
3. Compare 9 with largest. Since 9 is larger, update largest to 9.
4. Compare 2 with 9. Keep largest as 9.
5. Compare 7 with 9. Keep largest as 9.
6. Return 9, the largest value in the list.

Writing down the changing values is called a trace. A trace helps you check the logic by hand before translating it into code.

Make every step precise

A computer follows instructions literally. “Find the biggest number” is a goal, but it does not yet explain what to do. “Start with the first number, compare each remaining number, and replace the saved number when a larger one is found” is a sequence of steps that can be followed.

A good beginner algorithm should:

• Say what input it expects and what output it returns.
• Initialize the values it will use before reading or changing them.
• Describe decisions and repetitions clearly.
• Consider boundary cases, such as an empty list or a list with one item.
• Finish after a limited number of steps for the inputs it accepts.

A second example: search for a value

To search a short, unsorted list, check the items one at a time. If an item matches the value you want, report its position. If you reach the end without a match, report “not found.” This is called a linear search because it checks items in a line, one after another.

for each position in the list:
    if the item at that position equals the value we want:
        return that position
return "not found"

For a list of [4, 9, 2, 7], searching for 2 checks 4, then 9, then 2, and stops when it finds a match. If we search for 5, it checks all four items and reports that the value is not there.

A first look at efficiency

Efficiency describes how much work or memory an algorithm uses as its input grows. For a list of four items, a linear search checks at most four items. For a list of one hundred items, it may check one hundred. The work grows with the list's length.

For now, focus on understanding the steps and checking that they give the right answer. Later, you can compare different algorithms for speed and memory use. A clever algorithm is not better if it is unclear or gives the wrong result.

Chapter 1: Describe how work grows

Algorithm analysis asks how resource use changes as the input gets larger. Let n describe input size—for example, the number of items in a list. We count a useful operation (such as a comparison) or estimate memory, rather than relying only on seconds from one particular computer.

Asymptotic notation

Big O describes an asymptotic upper bound on growth; Big Omega describes a lower bound; and Big Theta describes a tight bound when upper and lower growth match. These notations describe functions as input size grows, not exact run times. Big O is not automatically synonymous with “worst case”: first name the case being analyzed, then give its bound.

For example, scanning every item in a list takes a number of comparisons proportional to n, so it is O(n). If a loop repeatedly halves a search range, it takes about log₂ n steps, or O(log n). Constant factors and lower-order terms matter in practice, but asymptotic analysis helps explain why some approaches scale better.

Common growth classes

Class	Typical example	What growth suggests
O(1)	Read an array item by index	Work does not grow with the number of items
O(log n)	Binary search in sorted data	Each step shrinks the search space by a factor
O(n)	One pass through a list	Work grows in proportion to input size
O(n log n)	Merge sort	Common target for comparison sorting
O(n²)	Compare every pair; basic insertion/bubble sort worst case	Doubling input can roughly quadruple work
O(2ⁿ)	Try every subset	Often practical only for small inputs

These are simplified guides, not timing promises. Cache behavior, memory allocation, input shape, implementation language, and constant factors can change which implementation is faster for real workloads. Analyze time and extra space separately.

Chapter 2: Reusable ways to design algorithms

A design paradigm is a reusable way to organize a solution. It narrows the search for an algorithm; it does not remove the need to prove that the resulting steps solve the specific problem.

Brute force: start with a dependable baseline

Try every candidate and keep the valid or best one. Exhaustive search is often easy to explain and can serve as a correctness reference for small test inputs. Its cost may grow rapidly—for example, checking every subset of n items visits 2ⁿ possibilities.

Divide and conquer: solve smaller independent pieces

Split a problem into smaller instances, solve each recursively, then combine the results. Merge sort divides a list in half, sorts each half, and merges the sorted halves. Its recurrence is T(n) = 2T(n/2) + O(n), giving O(n log n) time and typically O(n) extra space for arrays.

merge_sort(items):
    if items has at most one element:
        return items
    split items into left and right halves
    return merge(merge_sort(left), merge_sort(right))

Greedy: make a locally attractive choice

A greedy algorithm commits to a choice that looks best now. It is efficient when the problem has the right structure, but local improvement alone is not a proof of global optimality. For coin values [1, 3, 4] and amount 6, choosing the largest available coin first gives 4 + 1 + 1; the optimal answer is 3 + 3. Greedy change-making therefore fails for this coin system.

Dynamic programming: remember overlapping subproblems

Dynamic programming is useful when a problem has overlapping subproblems and an optimal substructure: a larger solution can be assembled from smaller solutions. Define each subproblem precisely, write its recurrence, establish base cases, then compute in a safe order. Memoization caches recursive results; tabulation fills a table iteratively.

fib(n):
    if n <= 1:
        return n
    if memo[n] is not known:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

With caching, Fibonacci values through n are computed in O(n) time instead of repeatedly solving the same smaller cases. For optimization problems, a state must preserve enough information to make future decisions correctly; a vague or incomplete state is a common source of errors.

Backtracking: explore, reject, and undo

Build a candidate one decision at a time. If a partial candidate already violates a constraint, stop exploring that branch and undo the last choice. Backtracking is useful for puzzles, constraint satisfaction, and enumerating arrangements. It can still take exponential time when many candidates remain viable.

Randomized algorithms: use randomness deliberately

A randomized algorithm uses random choices to influence its execution. Randomized quicksort, for example, has expected O(n log n) time under standard assumptions, while its worst case remains O(n²). Keep expected behavior, worst-case guarantees, and reproducibility distinct when evaluating such a method.

Chapter 3: Search and sorting

Choose a search that matches the data

Linear search checks items in sequence and works on unsorted data in O(n) time. Binary search repeatedly discards half the remaining range, taking O(log n) time—but only when the data is ordered and the search can access the middle efficiently. Sorting data first has a cost, so binary search is not automatically preferable for a single lookup.

binary_search(sorted_items, target):
    low = 0
    high = length(sorted_items) - 1
    while low <= high:
        middle = low + floor((high - low) / 2)
        if sorted_items[middle] == target:
            return middle
        if sorted_items[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return "not found"

The sorted-input requirement is part of the algorithm's contract, not an optional optimization. Using the midpoint formula shown also avoids an unnecessary risk of overflowing low + high in fixed-width integer languages.

Sorting: order data to make later work easier

Sorting places values into an order defined by a comparison rule. Besides producing a sorted list, it can enable efficient search, simplify duplicate detection, and make data easier to inspect. Algorithms differ in time, memory, stability (whether equal-key items retain their order), and whether they work in place.

Algorithm	Best / average / worst time	Extra space	Useful note
Insertion sort	O(n) / O(n²) / O(n²)	O(1)	Simple; effective on small or nearly sorted lists
Merge sort	O(n log n) / O(n log n) / O(n log n)	O(n)	Stable in common implementations; good predictable bound
Quicksort	O(n log n) / expected O(n log n) / O(n²)	Typically O(log n) stack on balanced splits	Often fast in practice; pivot strategy affects behavior
Heap sort	O(n log n) / O(n log n) / O(n log n)	O(1)	In-place with a reliable worst-case time bound

Bounds depend on the exact variant and input assumptions; “in place” and “stable” are properties of implementations, not consequences of a name alone. For general comparison sorting, the decision-tree argument gives a lower bound of Ω(n log n) comparisons in the worst case. Specialized methods can beat that bound when they exploit additional assumptions about keys.

Chapter 4: Model relationships with graphs

A graph represents entities as vertices and relationships as edges. Edges may be directed or undirected, weighted or unweighted. This model describes road networks, dependencies between tasks, links between web pages, and connections in social networks. An adjacency list stores each vertex's neighbors and uses O(V + E) space for V vertices and E edges.

Traversal and paths

• Breadth-first search (BFS) explores a graph level by level using a queue. It finds shortest paths by number of edges in an unweighted graph and takes O(V + E) time with adjacency lists.
• Depth-first search (DFS) follows a path until it cannot continue, then backtracks. It supports reachability, cycle detection, and topological sorting of directed acyclic graphs.
• Dijkstra's algorithm finds shortest paths from one source when edge weights are nonnegative. With an adjacency list and binary heap, a common bound is O((V + E) log V). Negative edge weights violate its key assumption; other methods are needed.
• Minimum spanning tree algorithms, such as Kruskal's and Prim's, connect all vertices of a connected weighted undirected graph with minimum total edge weight. A spanning tree is not the same task as shortest paths from one source.

Always state the graph representation and assumptions when quoting performance. A dense adjacency matrix uses O(V²) space and may be convenient when most vertex pairs are connected; a sparse adjacency list is usually more space-efficient.

Chapter 5: Reason about correctness

An algorithm is correct only relative to a precise specification: the allowed inputs and the required output for each input. A useful proof separates two questions: does the algorithm produce the right result, and does it eventually stop?

Loop invariants

A loop invariant is a statement that remains true at each iteration. For the largest-number scan, after processing the first k items, the variable largest is the maximum of exactly those k items.

1. Initialization: after the first item, largest is the maximum of the one-item prefix.
2. Maintenance: comparing the next item and updating when it is larger makes the statement true for the longer prefix.
3. Termination: when the scan ends, the prefix is the whole list, so largest is the maximum of all items.

This proof also exposes the empty-list boundary: there is no first item with which to initialize the invariant. The algorithm must reject that input or define a different result contract.

Induction, counterexamples, and edge cases

Recursive algorithms are often proved by induction on input size: establish a base case, assume smaller instances are correct, and show that the recursive step combines them correctly. When a claim seems plausible, actively seek a counterexample: minimum-size input, duplicates, already sorted or reverse-sorted data, disconnected graphs, equal priorities, and values at numeric limits.

Testing can find mistakes but cannot prove correctness for every possible input. Pair example-based tests with boundary tests, randomized tests, and—where possible—properties that should always hold. For a sorting algorithm, useful properties include nondecreasing output and preservation of the input's multiset of values.

Chapter 6: Turn an idea into a dependable implementation

1. Specify the contract. Define input types, valid ranges, output, error behavior, and whether mutation is allowed.
2. Choose a representation. Arrays, hash tables, trees, and graphs change the cost of operations. Choose based on the operations the solution actually needs.
3. Write a simple baseline. A clear, correct approach gives you something to test against before optimizing.
4. Prove the key step. Use an invariant, induction, or an exchange argument for greedy choices. State assumptions explicitly.
5. Analyze time and space. Include input size and relevant structure—for example, both vertices and edges for a graph.
6. Test representative and adversarial inputs. Include empty, singleton, duplicate, large, and invalid cases as appropriate to the contract.
7. Measure before tuning. Benchmark realistic workloads; preserve correctness while improving the actual bottleneck.

Prefer iterative solutions when recursion depth can grow with untrusted input. Check arithmetic for overflow, define behavior for missing values, and avoid assuming input is sorted or well-formed unless the interface guarantees it.

Chapter 7: Limits, responsibility, and open problems

Some problems have no known efficient exact algorithm. The class P informally captures decision problems solvable in polynomial time; NP captures decision problems whose proposed solutions can be checked in polynomial time. Whether P = NP remains an open question. NP-complete problems are among the hardest problems in NP: a polynomial-time algorithm for one would yield polynomial-time algorithms for all problems in NP.

For difficult optimization problems, practical alternatives include approximation algorithms with a stated quality guarantee, heuristics that trade guarantees for speed, parameterized methods that are efficient for small structural parameters, and exact algorithms for bounded input sizes. Explain what guarantee is sacrificed rather than presenting a heuristic result as optimal.

Algorithmic choices also have human consequences. Training data may reflect historical bias; a metric can reward the wrong behavior; an automated decision may be difficult to contest. Evaluate who benefits, who bears the errors, what data is collected, and whether people can understand or appeal the outcome. A mathematically correct implementation can still be an inappropriate system.

A compact glossary

Invariant

A statement that remains true through each step or iteration.

Recurrence

An equation describing a problem's cost in terms of smaller instances.

Stable sort

A sort that preserves the relative order of equal-key items.

Amortized analysis

A bound on average cost per operation across a sequence, even if some individual operations are expensive.

Heuristic

A practical method for finding good solutions without a general proof of optimality.

Questions for further study

1. When would sorting once and then using binary search beat repeated linear searches? Include the sorting cost in your comparison.
2. Which state and recurrence would model the minimum number of coins for an arbitrary set of denominations?
3. Why does Dijkstra's algorithm fail with negative edge weights? Construct a small counterexample.
4. How would you test that a graph traversal visits every reachable vertex exactly once?
5. Find an automated decision system and identify its objective, data assumptions, error costs, and appeal process.

References and further reading

This chapter synthesizes standard introductory material; the resources below provide fuller treatments, formal definitions, and lecture notes.

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 4th edition. MIT Press, 2022. Publisher information.
2. MIT OpenCourseWare. 6.006 Introduction to Algorithms, course materials and lecture notes. Course site.
3. Paul E. Black, ed. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Reference index.
4. Steven S. Skiena. The Algorithm Design Manual, 3rd edition. Springer, 2020. Publisher information.

Try it yourself

1. Trace the largest-number algorithm with [8, 3, 10, 6]. Write down largest after each comparison.
2. What should the largest-number algorithm do when its input list is empty? Why should it check this before reading the first item?
3. Trace the linear search for 7 in [4, 9, 2, 7]. How many items does it check?
4. Write steps for counting how many values in a list are greater than zero. What value should the counter start at?

Remember: define the task, identify the input and output, initialize your values, write small ordered steps, and test the plan with a hand trace.