A backtest that rebuilds a top- signal ranking by re-sorting the full universe every bar, and one that maintains the ranking in a heap, compute the same answer — the difference only shows up as the universe or the history grows, and "it ran fine on my laptop" is not a way to see that difference coming. This note fixes the vocabulary for talking about that difference precisely: an algorithm as a well-defined computational procedure, running time as a function of input size , and asymptotic notation (, , ) as the formal apparatus for comparing running-time functions while ignoring the constant factors and lower-order terms that depend on the machine, not the algorithm. The worked vehicle throughout is insertion sort, whose best and worst cases already illustrate why a single number ("it took 2ms") is the wrong unit of comparison, and every later topic in this unit states its results in exactly this notation.
Learning objectives. By the end of this note you should be able to:
- describe an algorithm's input size and running time as functions, and identify an algorithm's best-, worst-, and average-case behaviour;
- state the formal , , definitions and verify a claimed bound directly from them;
- classify a small piece of pseudocode's running time by counting the dominant operations;
- explain, with a concrete threshold, when a lower-order or constant-factor difference between two algorithms actually matters in practice.
In this lesson
- What an algorithm is, and how to measure it
- Asymptotic notation
The full lesson, with worked examples and exercise solutions, is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or explore the curriculum.