Big O Notation

This lesson covers Big O notation — the standard way to express the efficiency of algorithms in terms of time and space. Understanding algorithmic complexity is essential for the OCR A-Level Computer Science (H446) specification.

---

Why Measure Efficiency?

Two algorithms can solve the same problem but differ dramatically in how long they take or how much memory they use. Measuring efficiency allows us to:

• Compare algorithms objectively.
• Predict how an algorithm will scale as input size grows.
• Choose the best algorithm for a given problem.

---

What is Big O Notation?

Big O notation describes the worst-case (or upper bound) growth rate of an algorithm's resource usage (time or space) as the input size n grows towards infinity.

It focuses on the dominant term and ignores:

• Constants (e.g., 3n becomes O(n))
• Lower-order terms (e.g., n^2 + 5n + 10 becomes O(n^2))

---

Common Time Complexities