Is the most common way to express time complexity.
Big O Notation
It describes the worst-case scenario for an algorithm, giving an upper bound on its running time. This helps you predict how the algorithm will perform on a large dataset
Big O Notation
What are the most common Big O notations?
O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
O(n!)
The number of operations is constant and doesn’t depend on the size of the input
O(1) Constant Time
The running time grows very slowly as the input size increases
O(log n) Logarithmic Time
The running time grows proportionally to the size of the input
O(n) Linear Time
The running time grows faster than linear but slower than quadratic
O(n log n) - Log-Linear Time or Linearithmic Time
The running time is proportional to the square of the input size
O(n^2) Quadratic Time
The running time grows at an incredibly fast rate. This usually seen in algorithms that generate all permutations of a set
O(n!) Factorial Time
What examples is this, Accessing a single element in an array
Constant Time or O(n)
What example is this, Binary search
O(log n) Logarithmic Time
What example is this Traversing an array or a linked list
O(n) Linear Time
What example is this Efficient sorting algorithms like quicksort and merge sort
O(n log n) Linearithmic or Log-Linear Time
What example is this Nested loops that iterate over the entire input for each element, such as in bubble sort.
O(n^2) Quadratic Time
The Travelling Salesman Problem using a brute-force approach
O(n!) Factorial Time
Why is Complexity Important?
Performance Prediction
Algorithm Comparison
Scalability
It allows you to predict how an algorithm will behave as the input size grows without needing to run it. This is especially important for large-scale data processing
Performance Prediction
It provides a standardized way to compare the efficiency of different algorithms designed to solve the same problem. This helps you choose the most optimal one for your use case
Algorithm Comparison
it helps you assess how well an algorithm will scale. An algorithm with O(n) complexity is much more scalable for large inputs than one with O(n^2) complexity
Scalability
