Big O notation describes how the runtime of an algorithm grows as the input size increases. It is essential knowledge for A-Level Computer Science.
What is Big O?
Big O notation describes the worst-case scenario for an algorithm. It tells us how the number of operations scales with input size n.
Common Time Complexities
- O(1) - Constant time: The operation takes the same time regardless of input size
- O(log n) - Logarithmic: Binary search is a classic example
- O(n) - Linear: Simple loops that process each element once
- O(n log n) - Linearithmic: Efficient sorting algorithms like merge sort
- O(n squared) - Quadratic: Nested loops, bubble sort
- O(2 to the power n) - Exponential: Very slow, often seen in brute force solutions
Analysing Algorithms
To determine Big O: 1. Count the basic operations 2. Express this as a function of n 3. Keep only the dominant term 4. Drop constants
Why It Matters
Understanding time complexity helps you choose the right algorithm for the job and write efficient code that scales well.
