Learning path

Analysis of algorithms

Measure how running time and memory grow, solve recurrences, reason about average and amortized cost, and prove a loop correct.

About this subject

Analysis of algorithms asks two questions about a procedure: is it correct, and how do its time and memory grow as the input gets larger? Instead of timing one run on one computer, you count operations and compare growth rates with asymptotic notation: O for an upper bound, Ω for a lower bound, and Θ for a tight bound.

This path covers growth rates, recurrences and the master theorem, amortized analysis, best, worst, and average cases, loop invariants for correctness, and the trade-off between time and memory. Each lesson uses a small, complete program that runs on its own. Python has the full sequence. The other languages listed below add lessons that use that language's own idioms and standard library, such as Java threads, C++ smart pointers, C# LINQ, or Node.js streams, and appear only for the topics the language supports. The programs are simplified models chosen to make an idea visible, so they are a foundation for further study rather than a replacement for a full course or for production-grade software.

Before you start: Programming fundamentals and the complexity lesson in data structures and algorithms.

1
Python
Readable code for automation, data, and first programs.
Growth rates and asymptotic notation
Count operations to see how logarithmic, linear, and quadratic work grow with input size.
Recurrences and the master theorem
Describe divide-and-conquer cost with a recurrence and check it against its closed form.
Amortized analysis
Show that an occasional expensive step still gives constant average cost per operation.
Best, worst, and average case
Measure comparisons for lucky, unlucky, and typical inputs to the same algorithm.
Correctness with loop invariants
Prove that insertion sort is correct by checking an invariant before every iteration.
Time–space trade-offs with memoization
Spend memory on a cache to turn exponential recursion into linear work.
2
C
Learn memory, pointers, and efficient systems programming.
C: best, worst, and average case of linear search
Count comparisons to see how the cost of one algorithm depends on the input it receives.
C: amortized cost of a growing array
Double the capacity of a malloc'd array when it fills, and count the copies made.
3
C++
Build fast applications with modern types and classes.
C++: best, worst, and average case of linear search
Count comparisons to see that one algorithm can have different costs on different inputs.
C++: amortized cost of a growing array
Count the copies made by a doubling array to see why push_back is amortized constant time.
4
Java
Understand object oriented programs and the JVM.
Java: counting operations to see growth rates
Count loop iterations instead of timing them to compare linear, quadratic, and logarithmic growth.
Java: amortized cost of a growing array
Show that doubling a backing array makes append cost O(1) on average even though some appends copy everything.
5
C#
Build typed applications on .NET.
C#: best and worst case of insertion sort
Count comparisons on sorted, reversed, and mixed input to see how input order changes the cost.
C#: watching List<T> grow geometrically
Observe the capacity of a List<int> as items are added and see that reallocations become rarer.
6
JavaScript
Add behavior to the web and build applications.
JavaScript: memoization trades memory for time
Count the calls made by a naive recursive Fibonacci and a memoized one.
JavaScript: counting the steps of binary search
Show that searching a sorted array of 1000 items takes at most about ten comparisons.
7
TypeScript
JavaScript with static types for dependable code.
TypeScript: a typed memoize wrapper
Cache the results of a pure function with a generic higher-order function and count how often the body runs.

About this subject

Python

Growth rates and asymptotic notation

Recurrences and the master theorem

Amortized analysis

Best, worst, and average case

Correctness with loop invariants

Time–space trade-offs with memoization

C

C: best, worst, and average case of linear search

C: amortized cost of a growing array

C++

C++: best, worst, and average case of linear search

C++: amortized cost of a growing array

Java

Java: counting operations to see growth rates

Java: amortized cost of a growing array

C#

C#: best and worst case of insertion sort

C#: watching List<T> grow geometrically

JavaScript

JavaScript: memoization trades memory for time

JavaScript: counting the steps of binary search

TypeScript

TypeScript: a typed memoize wrapper