Big O Complexity Time Estimator
Estimate real-world execution time for common Big O complexity classes based on input size n and a single operation duration.
Fill in the fields above and click Calculate.
Formulas
Estimated Time = T(n) × top
Where T(n) is the operation count for complexity class and top is time per single operation (ns):
| Class | T(n) | Example |
|---|---|---|
| O(1) | 1 | Hash table lookup |
| O(log n) | log₂(n) | Binary search |
| O(√n) | √n | Primality test (trial division) |
| O(n) | n | Linear scan |
| O(n log n) | n × log₂(n) | Merge sort, heap sort |
| O(n²) | n² | Bubble sort, insertion sort |
| O(n³) | n³ | Naive matrix multiplication |
| O(2ⁿ) | 2ⁿ | Subset enumeration, TSP brute force |
| O(n!) | n! | Permutation generation |
Assumptions & References
- Operation count uses exact formulas: log₂(n) for logarithmic, √n for square root, n! computed exactly for n ≤ 170 (beyond that is infeasible), 2ⁿ for n ≤ 1023.
- The time per operation represents a single primitive operation (comparison, addition, memory access). Modern CPUs execute ~10⁹ simple operations per second, so 1 ns/op is a reasonable baseline.
- Big O notation describes asymptotic upper bounds; constant factors and lower-order terms are ignored. Real performance depends on hardware, cache behavior, compiler optimizations, and algorithm implementation.
- Feasibility thresholds: Instant (<1 ms), Very Fast (<1 s), Acceptable (<1 min), Slow (<1 hr), Very Slow (<1 day), Infeasible (≥1 day).
- Reference: Cormen, T. H., et al. Introduction to Algorithms, 4th ed. MIT Press, 2022.
- Reference: Knuth, D. E. The Art of Computer Programming, Vol. 1–4. Addison-Wesley.
- Reference: bigocheatsheet.com — complexity class comparisons.