Big-O Algorithm Complexity Comparison

Big-O notation describes how an algorithm’s runtime scales with input size n. It answers: if the input doubles, how many more operations does the algorithm need?

The five most common complexity classes, from fastest to slowest:

O(1): Constant time. The algorithm takes the same number of steps regardless of input size. Accessing an array element by index is O(1). Whether n is 10 or 10 million, you need exactly 1 operation.

O(log n): Logarithmic time. Operations grow proportional to the log of n. Binary search is the classic example. Doubling the input only adds one more comparison. At n = 1,000,000 you need about 20 operations.

O(n): Linear time. Each element is visited once. Scanning through an unsorted list is O(n). At n = 1,000,000 you need 1,000,000 operations in the worst case.

O(n log n): Linearithmic time. This is where the good general-purpose sorts live: merge sort, heapsort, and quicksort on average input. At n = 1,000,000 that is roughly 20 million operations.

O(n²): Quadratic time. Nested loops over the input. Bubble sort and insertion sort both sit here. The class function n² reaches 1,000,000 at n = 1,000 and 100,000,000 at n = 10,000, which is what this calculator reports.

A specific quadratic algorithm carries its own constant on top of the class. Bubble sort’s actual comparison count is about half of n², which is why the sorting step counter uses n(n-1)/2 and reports a smaller number than this page for the same n. Big-O deliberately throws that constant away, because it stops mattering as n grows.

The gap is why algorithm choice matters so much in practice. Bubble sort on a million items makes about 500 billion comparisons. Merge sort finishes the same job in roughly 20 million. Same hardware, same data, 25,000 times the work.

O(2^n) and O(n!) are a different league again. At n = 50, 2^n is about 1.1 quadrillion operations: near enough two weeks of solid work for one core running a billion operations a second. At n = 100 it is 1.3 × 10^30, and no amount of hardware rescues that. Factorial is worse still, with 20! already past 2 quintillion. Both classes are perfectly usable for small n and hopeless past roughly 40.