See, in concrete step counts and times, how much the running time differs as the data grows when algorithms have different time complexities (Big-O notation). Enter the data size and the number of operations a computer can perform per second to see the time each complexity class takes. You can also estimate the running time when the data size changes.
Favorites and recently used calculators are stored only in this browser (localStorage).
Steps and time by complexity class
Data size and number of steps (logarithmic vertical axis)
Step counts are calculated from the complexity expressions themselves, ignoring coefficients and constant terms (log is base 2). Actual times vary with coefficients, memory and cache speed, the order of the input and so on, so use them as rough guides. The chart shows data sizes up to 60 and is cut off above 10¹² steps.
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
What is Big-O notation?
Big-O notation (O notation) describes the rate at which the number of steps of an algorithm grows as the data size n becomes large. For example, if an algorithm takes 3n² + 5n + 2 steps, the n² term dominates for large n, so the coefficients and smaller terms are ignored and it is written O(n²). This makes it possible to compare the efficiency of algorithms independently of the computer's speed and the details of the implementation.
The difference complexity makes
At 100 million operations per second, for n = 1 million, O(n) takes 0.01 seconds and O(n log n) about 0.2 seconds, but O(n²) takes 10,000 seconds (about 2.8 hours). O(2ⁿ) takes about 130 days even for n = 50, and the time doubles each time n increases by 1. While the data is small, everything finishes in an instant and the differences are hard to see; they only become a problem as the data grows. Change the data size to 1000, 1 million and 1 billion and compare the time column of the table.
Estimating running time
If you know the time complexity, you can estimate the running time when the data size changes. If an O(n²) program takes 0.5 seconds for 1000 items, then for 4000 items the step count grows (4000 ÷ 1000)² = 16 times, so you can estimate about 8 seconds. For O(n log n), it grows 4000 × log₂ 4000 ÷ (1000 × log₂ 1000) ≒ 4.8 times, giving about 2.4 seconds. Exams often ask for estimates like this or for the order of complexity classes from fastest to slowest.
Time complexity of common algorithms
Binary search halves the range to examine each time, so it is O(log n). Comparison sorting is known to be impossible to do faster than O(n log n) in the worst case, and merge sort and heapsort reach this limit. Naive multiplication of n × n matrices is O(n³). Exponential-time algorithms such as O(2ⁿ) and O(n!) do not finish in a realistic time once n exceeds a few dozen, so dynamic programming, approximation algorithms and similar techniques are used to reduce the number of steps.
The number of pairs compared is (n−1) + (n−2) + … + 1 = n(n−1)/2: 45 for n = 10 and 499,500 for n = 1000. Big-O notation only describes how the count grows as n gets large, so the factor of 1/2 and the lower-order term are dropped, giving O(n²). Doubling n roughly quadruples the count. O(n) is the complexity of looking at each element once, and O(n log n) is that of algorithms such as merge sort that repeatedly split the data in half.
With O(n²), the running time is proportional to the square of the data size, so four times the data takes 4² = 16 times as long: 0.5 s × 16 = 8 s. 2 seconds would be the result for O(n), which is proportional to the data size, and 32 seconds for O(n³), which grows with the cube (4³ = 64 times). In practice it can be even slower, for example once the data no longer fits in the cache.
If the target is at position k, the search makes k comparisons, so the average is (1 + 2 + … + 100) / 100 = 50.5, or (n + 1)/2 in general. The best case (target at the front) takes 1 comparison and the worst case (target at the end) takes 100; both the average and the worst case are proportional to n, so the complexity is O(n). About 7 corresponds to log₂ 100 ≈ 6.6, the number of steps of a binary search, which cannot be used unless the data is sorted.
Each comparison roughly halves the search range, and 2¹⁰ = 1024 ≥ 1000, so the range is used up after at most 10 comparisons (⌊log₂ 1000⌋ + 1 = 10). The complexity is O(log n), and even 1,000,000 values need at most 20 comparisons. 32 corresponds to √1000 ≈ 31.6, and 500 is close to the average for a linear search (about n/2). Keep in mind, though, that binary search needs sorted data, and sorting itself costs O(n log n).
FAQ
What is the base of the log in O(log n)?
In Big-O notation a different base only changes the result by a constant factor, so the base is usually not written. This tool uses base 2 to match the step counts of binary search and similar algorithms.
Is an O(n²) algorithm always slower than an O(n log n) one?
When the data size is small, an O(n²) algorithm with a small coefficient can be faster. That is why real sorting implementations sometimes use insertion sort for short sections. As the data size grows, the lower complexity class always wins.
What is space complexity?
It describes how the amount of storage (memory) an algorithm uses grows. For example, merge sort uses working space for n items, so its space complexity is O(n), while heapsort rearranges the array in place, so it is O(1).
How does this come up in exams?
IT certification exams such as Japan's Fundamental Information Technology Engineer Examination often ask you to estimate the running time when the data size changes, to choose the time complexity of an algorithm, or to order complexity classes by size. You can check them by entering the numbers from the question in the “Estimate” section below.