DSA Big O Notation

Big O notation describes how the work of an algorithm grows when the input grows.

Why Not Just Use a Stopwatch?

The time a program takes depends on the computer, the language and other programs running. A fast laptop and an old phone give different times for the same code.

So instead we count how many steps an algorithm needs for an input of size n, and look at how that number grows as n gets bigger. This is called time complexity.

The Common Big O Classes

Big O	Name	Example	Steps for n = 1,000
O(1)	Constant	Get an item from a list by index	1
O(log n)	Logarithmic	Binary search	about 10
O(n)	Linear	Check every item once	1,000
O(n log n)	Linearithmic	Merge sort	about 10,000
O(n^2)	Quadratic	Compare every pair of items	1,000,000
O(2^n)	Exponential	Try every subset	too many to count

From best to worst: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n).

O(1): Constant Time

The work does not depend on n. Getting the first item takes one step whether the list has 5 or 5 million items.

Example

python

def first_item(items):
    return items[0]

print(first_item([10, 20, 30]))
print(first_item(list(range(1000000))))

Output

10
0

O(n): Linear Time

The work grows in step with n. Double the input, double the work.

Example

python

def total(items):
    s = 0
    for x in items:   # runs n times
        s += x
    return s

print(total([5, 10, 15, 20]))

Output

O(n^2): Quadratic Time

A loop inside a loop over the same data usually means O(n^2). With 1,000 items that is a million steps.

Example

python

def has_duplicate(items):
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

print(has_duplicate([3, 8, 1, 8]))
print(has_duplicate([3, 8, 1, 9]))

Output

True
False

O(log n): Logarithmic Time

The work grows very slowly, because each step cuts the problem in half. This counts how many times n can be halved:

Example

python

def halvings(n):
    steps = 0
    while n > 1:
        n = n // 2
        steps += 1
    return steps

print(halvings(1000))
print(halvings(1000000))

Output

9
19

A million items need only about 20 steps. You will see this in binary search.

Rules for Finding Big O

Drop constants: O(2n) is written O(n). We care about the shape of growth, not exact counts.
Keep the biggest term: O(n^2 + n) becomes O(n^2), because n^2 grows much faster.
Think worst case: Big O usually describes the worst input, for example the item you search for is last.
Loops add or multiply: two loops one after another are O(n + n) = O(n). A loop inside a loop is O(n × n) = O(n^2).

When someone says an algorithm "is O(n)", read it as "the work grows in a straight line with the input size".

Space Complexity

Big O also measures memory. A function that makes a new list as big as the input uses O(n) extra space. One that only keeps a few variables uses O(1) space, even for a huge input.

Exercise

What is the time complexity of a single loop that looks at every item of a list once?

O(1)O(log n)O(n)O(n^2)