Describe the efficiency of specific algorithms by calculating their Big O notation to analyse their scalability

What is Big O Notation?

Big O notation describes the upper bound of an algorithm’s growth rate — how time (or space) increases as input size ($n$) grows.

Time Complexity

Notation	Name	Growth	Example
O(1)	Constant	Stays the same regardless of $n$	Accessing array element by index
O(log n)	Logarithmic	Grows slowly as $n$ increases	Binary search
O(n)	Linear	Grows proportionally to $n$	Linear search, single loop
O(n log n)	Linearithmic	Slightly worse than linear	Merge sort, quick sort
O(n²)	Quadratic	Grows with $n^2$	Bubble sort, insertion sort, nested loops
O(n³)	Cubic	Grows with $n^3$	Triple nested loops
O(2ⁿ)	Exponential	Doubles with each increment to $n$	Recursive Fibonacci
O(n!)	Factorial	Worst growth — explodes rapidly	Generating all permutations

Big O Growth Chart

n!
O(2ⁿ)
O(n³)
O(n²)
O(n log n)
O(n)
O(log n)
O(1)
         ↑
    Growth slows as n increases

Space Complexity

Space complexity measures how much extra memory an algorithm needs relative to input size.

Notation	Name	What it means	Example
O(1)	Constant	Fixed memory, does not grow with $n$	Single variable, loop counter
O(log n)	Logarithmic	Memory grows with $\log n$	Recursive binary search
O(n)	Linear	Memory grows with $n$	Creating a new array, hash table
O(n²)	Quadratic	Memory grows with $n^2$	2D array / nested list creation