Set your Publisher ID in src/config/ads.ts to display live ads.
Big-O Notation & Algorithmic Complexity
Time complexity, space complexity, and comparing O(1), O(log n), O(n), and O(n²)
Big-O notation describes the limiting behavior of an algorithm as input size n grows toward infinity, measuring execution time scaling and memory consumption.
The Common Big-O Complexities
O(1) Constant: Operation takes identical time regardless of dataset size (e.g. array lookup by index, hash map key access).
O(log n) Logarithmic: Input size is halved at each step (e.g. Binary Search). Extremely scalable: searching 1 billion items takes just ~30 operations!
O(n) Linear: Execution time grows in direct 1:1 proportion with input size (e.g. single loop through array).
O(n log n) Linearithmic: The fastest theoretical comparison sort bound (e.g. MergeSort, QuickSort).
O(n²) Quadratic: Nested loops over the input (e.g. BubbleSort). Avoid for large datasets!
| Notation | Name | Operations for n = 1,000,000 | Verdict |
|---|---|---|---|
| O(1) | Constant | 1 operation | Optimal |
| O(log n) | Logarithmic | ~20 operations | Exceptional |
| O(n) | Linear | 1,000,000 operations | Good |
| O(n log n) | Linearithmic | ~20,000,000 operations | Acceptable for Sorting |
| O(n²) | Quadratic | 1,000,000,000,000 operations | Dangerous / Slow |
Set your Publisher ID in src/config/ads.ts to display live ads.
Test Yourself With Exercise
Approximately how many comparison operations does Binary Search take to locate an item in a sorted array of 1,000,000 elements?