O(1): constant
Work does not depend on input size.
def first(items):
return items[0]Reference
Big O basics
Big O describes how the work an algorithm does grows as the input size n grows. It ignores constants and lower-order terms, so it tells you which algorithm wins on large inputs, not which one is faster on ten items. Change n below to see how the growth classes pull apart.
At n = 20, O(1) does about 1 operations. At n = 20, O(log n) does about 4.3 operations. At n = 20, O(n) does about 20 operations. At n = 20, O(n log n) does about 86.4 operations. At n = 20, O(n²) does about 400 operations and leaves the top of the chart at n = 15. At n = 20, O(2ⁿ) does about 1,048,576 operations and leaves the top of the chart at n = 8.
| Complexity | Operations | Estimated time at 10⁸ operations per second |
|---|---|---|
O(1)Constant | 1 | 10 ns |
O(log n)Logarithmic | 4.3 | 43 ns |
O(n)Linear | 20 | 200 ns |
O(n log n)Linearithmic | 86.4 | 864 ns |
O(n²)Quadratic | 400 | 4.0 µs |
O(2ⁿ)Exponential | 1,048,576 | 10 ms |
Logarithms are base 2. In the linear view the chart clips at the top, so the steepest curves leave the plot early. Switch the operations axis to logarithmic to keep every curve in view, or type a larger n to see the table values diverge. Time estimates divide the operation count by an assumed 108 simple operations per second. They are not measurements: hardware, the language runtime, constant factors, memory access, and the input all change real running time.
Code for each class
O(log n): logarithmic
Each step discards half of what remains.
def binary_search(items, target):
lo, hi = 0, len(items) - 1
while lo <= hi:
mid = (lo + hi) // 2
if items[mid] == target:
return mid
if items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1O(n): linear
One pass over the input.
def total(items):
result = 0
for x in items:
result += x
return resultO(n log n): linearithmic
Sorting dominates, then one linear pass.
def has_duplicates(items):
items = sorted(items)
return any(a == b for a, b in zip(items, items[1:]))O(n2): quadratic
A loop inside a loop over the same input.
def has_pair_sum(items, target):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] + items[j] == target:
return True
return FalseO(2n): exponential
Every item doubles the number of branches.
def count_subsets(items, target, i=0):
if i == len(items):
return 1 if target == 0 else 0
take = count_subsets(items, target - items[i], i + 1)
skip = count_subsets(items, target, i + 1)
return take + skipColor key
O(1)O(log n)O(n)O(n log n)O(n2)O(2n)N/A or not applicable
Reading the notation
O(...)describes an asymptotic upper bound.Ω(...)describes an asymptotic lower bound.Θ(...)describes a tight asymptotic bound.nis the input size. Graph algorithms useVfor vertices andEfor edges. Some algorithms use extra parameters, such askorm, as noted in each table.α(n)is the inverse Ackermann function. It grows so slowly that it is at most 4 for any practical input.- Average (expected) cost depends on a stated assumption, such as random input or a well-behaved hash function. Amortized cost is the average per operation over a worst-case sequence of operations and involves no randomness. Worst-case cost is the most a single operation can take. See the notes under the data structure table.
- Tables use Θ where a bound is known to be tight, O for upper bounds, and Ω for lower bounds.
N/Ameans the operation is not applicable in that table's context.
Complexities are quick-reference summaries. Actual performance depends on the implementation, the input, and the assumptions behind each operation, so check the linked references when exact guarantees matter.