General
Understanding time complexity - a beginner's guide
7/2/2025
00
I see many beginners struggle with time complexity so here's a simple guide:
O(1) - Constant: HashMap lookup, array access by index
O(log n) - Logarithmic: Binary search, balanced BST operations
O(n) - Linear: Single loop through array
O(n log n) - Merge sort, heap sort
O(n²) - Quadratic: Nested loops (brute force)
O(2ⁿ) - Exponential: Recursive solutions without memoization
Quick rules:
- n ≤ 20 → O(2ⁿ) is fine
- n ≤ 1000 → O(n²) works
- n ≤ 10⁶ → Need O(n log n) or better
- n ≤ 10⁸ → Need O(n)
Hope this helps someone!
time-complexitybeginnertutorialdsa