Asymptotic Notation
Asymptotic notation provides a formal vocabulary for describing how the performance of an algorithm behaves as the input size grows toward infinity. The wo...
The Language Mathematicians and Engineers Use to Compare Algorithms
Asymptotic notation provides a formal vocabulary for describing how the performance of an algorithm behaves as the input size grows toward infinity. The word asymptotic refers to approaching a value without necessarily reaching it; in this context it means we care about the trend for large n, not the exact count for small n.
The three most common asymptotic notations are Big O, Big Omega, and Big Theta. Big O notation gives an upper bound on the growth rate. Saying an algorithm is O(f(n)) means its running time grows no faster than f(n) times some constant for sufficiently large n. Big Omega gives a lower bound: the algorithm takes at least c times f(n) steps for large n. Big Theta is the tightest description; it means the algorithm grows at exactly the rate of f(n) up to constant factors.
To say that linear search is O(n) is accurate but also technically correct to say it is O(n^2), since n is also bounded above by n^2. However, the convention is to use the tightest upper bound that is true. Saying O(n) is more informative than O(n^2) for linear search, so that is the preferred statement.
Asymptotic notation ignores constant factors and lower-order terms because for large inputs these matter far less than the dominant term. The function 1000n is still O(n) even though the constant is large. When n is small, 1000n might exceed n^2 for small n, but asymptotically, n^2 grows faster. Real-world performance still cares about constants, but asymptotic notation is designed for comparing algorithmic families at scale.
Asymptotic analysis applies to both time and space. An algorithm described as O(n) time and O(1) space is linear in time and constant in space. These two dimensions are independent and both matter for practical use.
Worked example: consider two sorting algorithms. Insertion sort has a worst-case time of O(n^2). Merge sort has a worst-case time of O(n log n). For n equal to ten, the difference is negligible. For n equal to one million, merge sort performs roughly one million times fewer operations in the worst case. Asymptotic analysis predicted this gap correctly.
Interview tip: never confuse O(1) average case with O(1) worst case. Hash table lookup is O(1) average but O(n) worst case due to collisions. Always specify which case you are describing.