Algorithm Efficiency using Big O Notation (OCR A-Level Computer Science): Revision Notes
Algorithm Efficiency using Big O Notation
Overview
Big O Notation is a mathematical way to describe the efficiency of an algorithm, focusing on how the algorithm's performance scales with the size of the input. It helps in comparing different algorithms by providing a high-level understanding of their time and space requirements, particularly as the input size grows.
What is Big O Notation?
- Big O notation expresses the upper bound of an algorithm's growth rate, describing its worst-case scenario performance.
- It measures:
- Time Complexity: How execution time increases with input size.
- Space Complexity: How memory usage increases with input size.
Common Big O Complexities
| Complexity | Notation | Description | Example Algorithm |
|---|---|---|---|
| Constant | O(1) | Performance is unaffected by input size. | Accessing an array element. |
| Logarithmic | O(log n) | Performance grows logarithmically as input size increases. | Binary search. |
| Linear | O(n) | Performance grows linearly with input size. | Linear search. |
| Polynomial | O(n²), O(n³), etc. | Performance grows polynomially with input size. | Bubble sort (O(n²)). |
| Exponential | O(2ⁿ) | Performance doubles with each additional input element. | Recursive Fibonacci. |
Interpreting and Recognising Big O on Graphs
Each Big O notation has a distinct shape when graphed (Input size on the x-axis and Time on the y-axis):
-
Constant Complexity (O(1)): A flat line—performance does not change with input size.
-
Logarithmic Complexity (O(log n)): A curve that rises quickly at first but flattens as the input grows.
-
Linear Complexity (O(n)): A straight line with a constant slope.
-
Polynomial Complexity (O(n²)): A parabolic curve—steeper growth than linear.
-
Exponential Complexity (O(2ⁿ)): A sharply rising curve—rapid growth as input increases.
Graph of Complexities
Below is an approximate visualisation of how different complexities grow:
| *
| * (O(2ⁿ) - Exponential)
| *
| *
| *
| * (O(n²) - Polynomial)
|*
| (O(n) - Linear)
|
| (O(log n) - Logarithmic)
|
| * * * * * (O(1) - Constant)
----------------------------------------------------
Input Size (n)
Examples of Big O Analysis
Example 1: Accessing Elements in an Array
- Task: Retrieve an element by its index.
- Complexity: O(1) (Constant time) because it takes the same amount of time regardless of array size.
Example 2: Binary Search
- Task: Search for an element in a sorted array by repeatedly halving the search space.
- Complexity: O(log n) (Logarithmic time) since each step reduces the problem size exponentially.
Example 3: Bubble Sort
- Task: Sort an array by repeatedly swapping adjacent elements.
- Complexity: O(n²) (Quadratic time) because it compares each element to every other element.
Example 4: Recursive Fibonacci
- Task: Calculate the nth Fibonacci number using recursion.
- Complexity: O(2ⁿ) (Exponential time) due to redundant calculations of the same subproblems.
How to Determine Big O Complexity
- Identify Loops:
- A single loop running n times is O(n).
- A nested loop (loop within a loop) over n is O(n²).
- Examine Recursive Calls:
- If each recursive call splits the problem in half (like binary search), it's O(log n).
- If recursion branches exponentially, it's O(2ⁿ).
- Simplify:
- Drop lower-order terms and constants.
- For example: If an algorithm runs in n + log n time, it simplifies to O(n).
Note Summary
Common Mistakes
- Ignoring Constants and Simplifying Too Soon:
- While constants don't affect Big O notation, they can impact performance for small inputs.
- Be cautious with small data sets when constants may have a noticeable impact.
- Overestimating the Worst Case:
- Not all operations occur in the worst case, e.g., Quick Sort has a worst-case of O(n²) but an average-case of O(n log n).
- Misinterpreting Logarithmic Growth:
- Logarithmic complexity grows slowly, even for large data, but depends on the base of the logarithm (often base 2 in CS).
Key Takeaways
- Big O notation measures an algorithm's efficiency in terms of time and space as input size increases.
- Recognise key complexities: Constant (O(1)), Logarithmic (O(log n)), Linear (O(n)), Polynomial (O(n²)), and Exponential (O(2ⁿ)).
- Use graphs to visualise and compare the growth of different complexities.
- Simplify Big O expressions by focusing on the most significant term and ignoring constants.