Asymptotic Notation describes how the running time of an algorithm changes as the input size grows.
It has three main types:
- Big-O (O) notation
- Indicates the maximum time an algorithm takes to run. It’s like an upper limit or worst-case scenario for a given input.
- Omega (Ω) notation
- Indicates the minimum time an algorithm takes to execute. It’s like a lower limit or best-case scenario for a given input.
- Theta (Θ) notation
- Indicates an average or typical scenario for an algorithm’s running time, falling between the best and worst cases.
To take insertion sort as an example:
- Big-O notion would calculate the time the insertion sort takes to sort a reverse sorted array.
- Omega notion would calculate the time the insertion sort takes to sort a sorted array.
- Theta notation would calculate the time the insertion sort takes to sort an average/random array.
Caveats:
- Big-O notation is commonly used to assess how an algorithm’s performance scales as the input size increases.
In summary, these notations give us a range of time complexities an algorithm might exhibit for different input scenarios, helping us understand its behaviour and efficiency.