Bars are scaled logarithmically (each class spans many orders of magnitude). “Operations” is the approximate work done. Rule of thumb: ~108 operations ≈ 1 second.
Complexity comparison table
Approximate operation counts. Green scales comfortably; red is only viable for tiny inputs.
| Complexity | n = 10 | n = 100 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|---|
| O(1) constant | 1 | 1 | 1 | 1 |
| O(log n) logarithmic | 3 | 7 | 10 | 20 |
| O(n) linear | 10 | 100 | 1,000 | 1,000,000 |
| O(n log n) | 33 | 664 | 9,966 | ~2×107 |
| O(n²) quadratic | 100 | 10,000 | 1,000,000 | 1012 |
| O(2ⁿ) exponential | 1,024 | ~1030 | ~10301 | astronomical |
| O(n!) factorial | ~3.6M | ~10158 | astronomical | astronomical |
Common operations → complexity
| Array index / hash lookup | O(1) |
| Binary search (sorted) | O(log n) |
| Single loop / linear scan | O(n) |
| Efficient sort (merge/heap/quick avg) | O(n log n) |
| Nested loops over the same input | O(n²) |
| Generate all subsets | O(2ⁿ) |
| Generate all permutations | O(n!) |
FAQ
What’s the order from fastest to slowest?
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). Everything up to O(n log n) scales well.
How large an input can each handle in ~1 second?
At ~108 ops/sec: O(n)/O(n log n) → 10M+, O(n²) → ~10,000, O(2ⁿ) → n≈26, O(n!) → n≈11.
Why is O(log n) so fast?
It halves the work each step. For a million items, log2 is only ~20 — binary search needs ~20 comparisons, not a million.
Is this free to share?
Yes — free, no signup, link it anywhere. Published by CoPilot Interview.
State your complexity with confidence
Interviewers expect you to analyze what you write — out loud, in real time. CoPilot Interview is a desktop AI assistant that surfaces the approach, the code, and the Big-O during live coding rounds, with a permanent free tier.
See how it works