01Overview

In 1894 Bachmann introduced O notation to describe how functions grow; it was Knuth who made it the language of algorithms. From 1968, in The Art of Computer Programming, he used asymptotic analysis, sums and generating functions systematically, freeing algorithm study from any particular machine.

Analysis is not just counting loops. The average case needs probabilistic assumptions, amortised analysis spreads the cost of a sequence of operations over each one, and lower bounds tell us when faster is impossible. Today complexity analysis is the first filter in engineering decisions — though before the data grows tenfold, constant factors and cache locality often matter more than the asymptotic order.

02History

  1. 1894

    Bachmann introduces O notation

    An upper bound on how fast a function grows.

  2. 1968

    Knuth systematises algorithm analysis

    The first volume of The Art of Computer Programming appears.

  3. 1973

    Amortised analysis

    Spread the cost of a whole sequence of operations across each one.

  4. 1970

    Decision-tree lower bounds

    Comparison sorting needs Omega(n log n).

03Core concepts

Asymptotic notation

O, Ω and Θ describe upper, lower and tight bounds on growth.

Average and worst case

The first depends on assumptions about input; the second gives a guarantee.

Amortised analysis

Spreads rare expensive operations across the whole sequence.

04Hands-on

Do it once — it beats reading it ten times

Time the same algorithm at n=1e3…1e6, then use log-log axes to decide whether it is n log n or n²

05Self-check

Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.

Can you explain "Asymptotic notation"?

O, Ω and Θ describe upper, lower and tight bounds on growth.

Can you explain "Average and worst case"?

The first depends on assumptions about input; the second gives a guarantee.

Can you explain "Amortised analysis"?

Spreads rare expensive operations across the whole sequence.

What problem did it solve, and why was there nothing better at the time?

Go back to the history section: how was this done before, and what did it cost?

If you had to build it today, how would you break it down?

Use the hands-on task above: write a plan of at most three steps before you start.

06Key people

D

Donald Knuth

1938 –

Author of The Art of Computer Programming and TeX.

P

Paul Bachmann

1837 – 1920

Introduced big-O notation.

07Further reading

  • The Art of Computer Programming, Volume 1Donald Knuth · 1968
  • Introduction to AlgorithmsCormen et al. · 1990