Big O Notation is used in computer science to describe the performance or complexity of an algorithm. It is a good practice for software engineers to understand in-depth as well.
How do you measure the efficiency of an algorithm?
There are several ways to measure the efficiency of an algorithm, some of the most common methods include.
- Time complexity: This measures the amount of time required for an algorithm to complete as a function of the size of the input. Time complexity is usually expressed using big O notation, which describes the upper bound of an algorithm's running time.
- Space complexity: This measures the amount of memory used by an algorithm as a function of the size of the input. Space complexity is also usually expressed using big O notation, which describes the upper bound of an algorithm's memory usage.
- Best, average, and worst-case time complexity: These measures describe the performance of an algorithm for different input scenarios. The best-case time complexity is the best performance an algorithm can achieve, the average-case time complexity is the expected performance of an algorithm for a random input, and the worst-case time complexity is the worst performance an algorithm can achieve.
- Benchmarking: This is a practical method of measuring the efficiency of an algorithm. It involves running the algorithm on a specific input and measuring the actual time and memory it takes to complete. This method can be used to compare the performance of different algorithms or to measure the performance of an algorithm on different input sizes.
It's important to note that choosing an appropriate algorithm depends on the specific use case, as different algorithms may be better suited for different types of problems and inputs.
Following are the common time and space complexities:
- Constant:
O(1) - Logarithmic:
O(log n) - Linear:
O(n) - Log-linear (Mix of linear and logarithmic):
O(n log n) - Quadratic:
O(n^2) - Exponential:
O(2^n) - Factorial time:
O(n!)
| Big O Notation | 10 Operations | 100 Operations | 1000 Operations |
| O(1) | 1 | 1 | 1 |
| O(log n) | 3 | 6 | 9 |
| O(n) | 10 | 100 | 1000 |
| O(n log n) | 30 | 600 | 9000 |
| O(n^2) | 100 | 10000 | 1000000 |
| O(2^n) | 1024 | 1.26e+30 | 1.07e+301 |
| O(n!) | 3628800 | 9.33e+157 | 40.02e+2567 |
But Why Do We Need Big O?
Big O notation is a way to express the upper bound of an algorithm's running time or space complexity, and it provides a way to compare the efficiency of different algorithms.
Big O notation provides a simplified way to express how the running time or space complexity of an algorithm grows as the size of the input increases. It describes the worst-case scenario, which is an upper bound of the actual running time or space complexity. This means that the algorithm will never take more time or space than what's described by its Big O notation, even though it might take less time or space for some inputs.
It's worth noting that Big O notation is not the only notation used to express the time/space complexity of an algorithm. Other notations such as Big Theta, Big Omega and Little o notation also used to express the complexity of an algorithm.
Last Update: 05 Dec, 2024