Skip to content
Tutorials Center
My learning

Topics

Lesson 57 of 68 ยท Computation and Languages

Algorithms, Recursion and Growth

Prove algorithms correct with loop invariants and induction, count operations, and compare growth rates from log n to 2^n with runnable Python.

An algorithm is a finite, precise recipe that turns an input into an output. Discrete mathematics asks two questions about every algorithm. First, is it correct: does it give the right answer for every valid input, not just the ones you tried? Second, how much work does it do: how does the running time grow as the input gets bigger? Both questions have mathematical answers, and you already own the tools. Correctness uses induction and its cousin, the loop invariant. Cost uses sums and recurrences.

This lesson is a compact tour. We prove small algorithms correct, count their operations exactly instead of timing them, watch recursion unfold, and compare growth rates until the difference between n log n and 2^n is impossible to forget. For the full toolkit of data structures and algorithm techniques, the DSA track goes much further.

Two questions about any algorithm

Is it correct? Right answer for every valid input.
How fast does it grow? Work as a function of input size n.
1 / 2

Correctness and loop invariants

An algorithm is correct when it terminates and its output meets the specification for all inputs. Testing can only show correctness on the examples you tried. A proof covers every input.

For loops, the standard technique is a loop invariant: a statement that is true before the loop starts and stays true after each iteration. The proof has three parts, which mirror induction:

  1. Initialization: the invariant is true before the first iteration.
  2. Maintenance: if it is true before an iteration, it is true after it.
  3. Termination: when the loop ends, the invariant plus the exit condition imply the result you want.

Take finding the maximum of a list. The invariant: after processing the first i items, best is the largest of them. Before any item, the list prefix is empty, so we start best with the first item and treat the invariant as true for one item. Each iteration compares one new item and keeps the larger, which maintains the invariant. When the loop ends, i = n, so best is the largest of all n items.

A good way to trust an invariant while you develop is to turn it into an assert that runs on every iteration. If you wrote the invariant wrongly, the assertion trips on a test run.

Python Loop invariants checked with assert

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Recursion and induction

A recursive algorithm solves a problem by calling itself on a smaller instance. Correctness has the shape of strong induction: prove the base case directly, then assume the recursive calls work on smaller inputs and show the combination works for the current one.

Merge sort is a standard example. To sort a list: if it has at most one item, it is already sorted (base case). Otherwise sort each half recursively (these are smaller, so by the induction hypothesis they come back sorted), and merge the two sorted halves into one sorted list. Since merging two sorted lists is correct, the whole thing is correct. See recursion and merge sort for more.

Recursion also makes it easy to waste work. The naive recursive Fibonacci recomputes the same values over and over. The number of calls itself follows a recurrence, calls(n) = calls(n-1) + calls(n-2) + 1, which grows as fast as the Fibonacci numbers do. Remembering results (memoization) removes the repeats.

Counting operations

Wall-clock timing depends on the machine, the language and what else is running. Mathematical analysis instead counts basic operations (usually comparisons) as a function of the input size n. That count is reproducible and does not depend on hardware.

We usually care about the worst case, the largest count over all inputs of size n, because it is a guarantee. Sometimes the average case or best case is also useful. For linear search the worst case is n comparisons, for binary search roughly logโ‚‚ n, and for bubble sort about nยฒ/2.

Python Counting comparisons exactly

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The table shows the pattern. Linear search grows in step with n; binary search barely moves, because each comparison halves the remaining range. Bubble sort grows about 100 times when n grows 10 times, the signature of nยฒ. Merge sort lands in between, near n logโ‚‚ n.

Big-O and comparing growth rates

Big-O notation describes how a function grows while ignoring constant factors and small terms. We say f(n) = O(g(n)) if for large enough n, f(n) is at most a constant multiple of g(n). So 3nยฒ + 5n + 2 = O(nยฒ). The common classes, from slowest to fastest growing:

Class Name Example
O(1) constant index into a list
O(log n) logarithmic binary search
O(n) linear scan a list
O(n log n) linearithmic merge sort
O(nยฒ) quadratic comparing every pair
O(2โฟ) exponential trying every subset
O(n!) factorial trying every ordering

Constants matter in practice, but growth rate decides what happens as inputs grow. An exponential algorithm that handles 30 items in a second needs a thousand seconds for 40 items and a million seconds for 50. The next demo makes that concrete: for a budget of 100 million steps, how large an input can each class handle? It also draws the curves.

Python How big an input can each growth rate handle?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the graph, the exponential curve leaves the chart almost immediately, while n log n and nยฒ stay manageable for a while. This is why computer scientists consider polynomial-time algorithms "feasible" and exponential-time ones suspicious, and why the question of whether hard problems like SAT have fast algorithms matters so much.

Recursion cost as a recurrence

When an algorithm calls itself, its cost satisfies a recurrence, and solving the recurrence gives the growth rate. Merge sort splits in half, recurses twice and merges in linear time, so T(n) = 2T(n/2) + n, which solves to ฮ˜(n log n); see solving recurrences. Naive Fibonacci satisfies calls(n) = calls(n-1) + calls(n-2) + 1, so the number of calls grows exponentially. You can check the closed form against a real run: the call count for fib(n) is 2ยทF(n+1) - 1.

Python Naive recursion versus memoization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive version makes 21,891 calls for fib(20); the memoized version does the body only 21 times, one per value from 0 to 20. Recursion is not the problem; repeated subproblems are. That observation is the heart of dynamic programming.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the three parts of a loop invariant proof?

    The invariant must hold before the loop, be preserved by each iteration, and imply the goal when the loop ends.
  2. 2. Binary search on a sorted list of 1,000,000 items needs about how many comparisons in the worst case?

    Each comparison halves the range and log2(1,000,000) is about 20.
  3. 3. Which is the fastest growing function?

    Exponential growth eventually beats every polynomial, so 2^n overtakes n^3 for large n.
  4. 4. Why does naive recursive Fibonacci take exponential time?

    fib(n) calls fib(n-1) and fib(n-2), which overlap heavily, so the number of calls grows like the Fibonacci numbers themselves.
  5. 5. If f(n) = 3n^2 + 5n + 2, which statement is correct?

    For large n the n^2 term dominates, and constants are ignored, so f(n) is O(n^2).

Summary

  • Correctness means the algorithm terminates with the right output on every input; a loop invariant (initialization, maintenance, termination) proves loops correct and induction proves recursion correct.
  • Count operations rather than seconds; analyze the worst case for guarantees.
  • Big-O ignores constants and lower terms: O(1), O(log n), O(n), O(n log n), O(nยฒ), O(2โฟ), O(n!) from slow to fast growth.
  • Exponential growth makes even moderate inputs infeasible, while n log n and nยฒ remain practical for large n.
  • A recursive algorithm's cost satisfies a recurrence; naive Fibonacci is exponential because of repeated subproblems, and memoization fixes it.

Next: Project: A Tiny SAT Solver, where logic, search and pruning come together.