Algorithm Complexity (Big-O)

Key idea

How running time grows with input size.

In depth

Big-O describes how running time grows with input size, ignoring constants: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). It compares algorithms at scale.

Worked example

Binary search is O(log n); scanning a list is O(n); nested loops over n items are O(n²).

Formula

Real-world uses

• Choosing between sorting methods for large datasets and predicting app performance

Common mistake

Assuming a smaller O always means faster on small inputs.

How to learn this

1. Read the key idea and say it in your own words.
2. Work through the worked example, then try a similar problem.
3. Use the interactive lesson’s visual and mini-quiz to check the pattern.

Frequently asked questions

Expand all Collapse all

Related expert topics in Discrete Math & Number Theory

• Strong Induction – Assume all earlier cases to prove the next.
• Well-Ordering Principle – Every nonempty set of positive integers has a least element.
• Partial Orders – Reflexive, antisymmetric, transitive relations.
• Cardinality of Sets – Comparing sizes of infinite sets.
• Countable and Uncountable Sets – ℕ and ℚ are countable; ℝ is not.
• Cantor’s Diagonal Argument – Proof that real numbers are uncountable.