On this page
Two programs can give the same answer and still differ by hours in how long they take. Measuring that difference with mathematics, before you run anything, is called the analysis of algorithms, and Donald Knuth did more than anyone to make it a subject. This post covers his life from reliable sources, counts the steps of two search methods in a worked example, and lists the mistakes students make with big-O notation.
Who is Donald Knuth?
The ACM's Turing Award biography records that Donald Ervin Knuth was born on 10 January 1938 in Milwaukee, Wisconsin. In high school he was interested in physics and good at mathematics, and a scholarship took him to the Case Institute of Technology in Cleveland to study physics. He switched to mathematics in his second year, partly because he had trouble with science labs. In December 1956 he spotted a newly installed IBM 650 computer across the hall from the statistics lab where he worked, and spent much of the next summer learning how it worked. Case awarded him a master's degree in mathematics when he finished his bachelor's.
How did The Art of Computer Programming begin?
In January 1962, while Knuth was a PhD student at Caltech, the publisher Addison-Wesley asked him to write a book on compilers. He sketched 12 chapters. Reading research for a chapter on sorting, he found the literature of the new field spotty and sometimes unreliable, and decided to write a book that organised what was known. By June 1965 his first draft had reached 3,000 handwritten pages.
The publisher split the work into volumes. Volume 1 of *The Art of Computer Programming* appeared in 1968, the year Knuth moved to Stanford, and volumes 1 to 3 were out by 1973. The ACM biography says the books emphasised a mathematical approach to comparing algorithms. When Knuth suggested renaming them *The Analysis of Algorithms*, the publishers said: "We can't; it will never sell." Knuth has said that developing the analysis of algorithms as an academic subject is his proudest achievement.
He received the ACM Turing Award in 1974, with a citation naming his book series, and the Kyoto Prize in 1996. His Turing lecture, Computer programming as an art, opens with gentle humour: programming had become a science "in a remarkably simple way: merely by deciding to call it 'computer science.'" Unhappy with the computer typesetting of a second edition, he began building the TeX typesetting system in 1977, and TeX's family of systems, including LaTeX, grew from it.
What does analysing an algorithm mean?
It means counting how many basic steps an algorithm takes as its input grows, and finding a formula for that count. Knuth also cared about stating such results precisely: his 1976 note Big Omicron and big Omega and big Theta in ACM SIGACT News is about the notations O, Ω and Θ that computer scientists use for growth rates.
Worked example: linear search against binary search
Suppose you look for one roll number in a sorted list of n = 1,000 numbers, and every position is equally likely.
Linear search checks items one by one. If the number is in position k, it takes k comparisons. The average over all positions is (1 + 2 + ... + n) ÷ n = [n(n + 1) ÷ 2] ÷ n = (n + 1) ÷ 2.
For n = 1,000: (1,000 + 1) ÷ 2 = 500.5 comparisons on average.
For n = 2,000: 1,000.5. Doubling the list doubles the work, so linear search is O(n).
Binary search checks the middle item, then discards the half that cannot contain the number. In the worst case it needs log₂ n rounded down, plus 1, comparisons.
For n = 1,000: log₂ 1,000 ≈ 9.97, which rounds down to 9, so at most 10 comparisons.
For n = 2,000: log₂ 2,000 ≈ 10.97, so at most 11. Doubling the list adds one step, so binary search is O(log n).
One more check on the notation. Suppose an algorithm takes f(n) = 3n² + 5n + 2 steps. For n ≥ 1, 5n ≤ 5n² and 2 ≤ 2n², so f(n) ≤ 10n². That makes f(n) = O(n²).
What mistakes do students make with big O?
Forgetting that binary search needs sorted data. On an unsorted list it fails, and sorting first has its own cost.
Keeping constants. O(3n²) is written O(n²); constants do not change the growth rate.
Judging by tiny inputs. For n = 5, a simple O(n²) method may beat a clever O(n log n) one. Big O is about large n.
Mixing up average and worst case. Say which one you mean.
Our post on searching and sorting in Python has code for both searches, and algorithms, flowcharts and pseudocode covers writing steps before code. If the sum formula in the worked example felt unfamiliar, the Fermi Concept Library covers every concept in physics, chemistry, biology, mathematics and computing, so you can revise the one idea that is blocking you.
What can a student learn from how Knuth worked?
Knuth noticed that his field's literature was patchy and unreliable, and set out to organise it carefully in one place. The ACM biography notes that he pays $2.56 for each error readers find in his books, and that many finders frame the cheque instead of cashing it. Treat your own notes the same way: when you find a mistake, fix it at the source so it does not survive into revision.
Try it now: find the worst-case number of comparisons for binary search on 1,000,000 sorted items, using log₂ 1,000,000 ≈ 19.93.
