Big O Notation

Big O notation describes how an algorithm's running time or memory use grows as the input gets larger, ignoring constant details. For example, O(n) grows in direct proportion to the input.

General Programming

It lets you compare algorithms independently of hardware. Common complexities, from fastest to slowest, include O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), and O(n^2) quadratic.

A loop over n items is O(n); a loop inside a loop over the same items is O(n^2).

Examples

Python

# O(n): one pass over n items
def contains(items, target):
    for item in items:
        if item == target:
            return True
    return False

print(contains([3, 7, 9], 7))

Output:

True

See also

Back to the Dictionary