Describes how run time or memory grows with input size.
Big-O describes how run time or memory scales with input size n, ignoring constants and lower-order terms: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). Worst-case, average and amortised analyses. It guides algorithm choice for large data.
Doubling n quadruples the work for an O(n²) algorithm.
Big-O notation tells you how an algorithm scales, which decides whether it will still be fast enough when the data grows.
Describes how run time or memory grows with input size.
Big-O notation tells you how an algorithm scales, which decides whether it will still be fast enough when the data grows.
Constant factors and lower-order terms, so it describes growth as the input becomes large rather than the exact run time.
Not always. For small inputs, a simpler algorithm with a worse Big-O may run faster in practice.
Typical applications include choosing a search method for a list of a million records, comparing two sorting algorithms for large data sets and estimating whether a nested loop will be fast enough for a dataset.
Study "Binary and data representation" first (topic 15 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Growth-rate hierarchy. Space complexity. Empirical profiling complements theory.
Doubling n quadruples the work for an O(n²) algorithm.
The next topic is "Linear and binary search", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 16 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.