Big O Notation
What is Big O Notation?
Big O Notation is a mathematical notation used to describe the upper bound of an algorithm's runtime. It gives us an idea of the worst-case scenario—the maximum amount of time an algorithm could take to complete as the input size grows.
Why Use Big O?
Understanding Big O notation helps developers choose the most efficient algorithm for a given problem, especially when scaling to large inputs. It simplifies comparing the efficiency of algorithms by focusing on their growth rates.
Common Big O Notations
| Notation | Description | Example |
|---|
O(1) | Constant time | Accessing an array element by index |
O(log n) | Logarithmic time | Binary search in a sorted array |
O(n) | Linear time | Looping through an array |
O(n log n) | Linearithmic time | Merge sort |
O(n^2) | Quadratic time | Nested loops |