Big O Notation

Big O notation is the way every data structure's costs are written: it says how the work an operation does grows as its input grows, without timing anything. It matters because growth, not speed on a small test, decides whether a program still works when its input is a thousand times larger. The topic starts with what Big O counts and why constants and smaller terms drop out, simplifies a cost by hand, and ranks the six growth classes you will meet most. It then turns a class into a time estimate, separates a bound from a case, and shows why a bare O(1) is not a promise. Reading a cost off real code, extra memory and costs with two inputs belong to Analysing Complexity, and amortised cost to Arrays and Strings; formal proofs are left out.