What Big O measures
Big O focuses on growth rather than an exact number of milliseconds. Constants and smaller terms matter in real systems, but the dominant term usually gives the clearest first comparison for large inputs.
Recognize common complexity classes
Direct access is often O(1), binary search is O(log n), one full pass is O(n), and two nested passes are often O(n²). Sorting with comparison-based algorithms commonly takes O(n log n).
- O(1): constant
- O(log n): logarithmic
- O(n): linear
- O(n log n) and O(n²)
Analyze code step by step
Define the input size, count the operations that grow with it, combine sequential work by addition, and multiply nested work. For recursion, include both the number of calls and the work done inside each call.
Remember space complexity
A faster solution may use an extra set, map, queue, or recursion stack. State both time and auxiliary space so the tradeoff is clear.