DSA What Is Big O

Big O is a label that describes how the work of a program grows when the input grows. The label names the shape of the growth, like straight or squared.

One pass over n items

A step is one small piece of work, like one visit to an item. One pass visits each item once, so n items take n steps.

n = 10
steps = 0
for i in range(n):
    steps += 1
print(steps)

Nested loops multiply the work

A loop inside a loop runs the inner work once for every outer item. Ten items paired with ten items give a hundred steps.

n = 10
steps = 0
for i in range(n):
    for j in range(n):
        steps += 1
print(steps)

Halving grows slowly

Halving cuts the remaining size in two at each step. A hundred items shrink to one in only six halvings.

n = 100
steps = 0
while n > 1:
    n = n // 2
    steps += 1
print(steps)

Example

def one_pass(n):
    steps = 0
    for i in range(n):
        steps += 1
    return steps

def nested(n):
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    return steps

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

n = 100
print("One pass:", one_pass(n))
print("Nested:", nested(n))
print("Halving:", halving(n))

Key points

Big O labels the growth of the work, not the exact step count of one run
O(1): the work stays the same when the input grows
O(n): the work grows in step with the input size
O(n^2): the work grows with the square of the input size
O(log n): the work grows by one step each time the input doubles

In this example, three functions each take the same input size of 100. The one-pass function counts one step per item and returns 100. The nested function counts one step per pair and returns 10000. The halving function counts one step per halving and returns 6. The three counts show three very different shapes of growth at the same input size.

Note

The letter in Big O is a capital letter O, not the number zero.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def one_pass(n):
    steps = 0
    for i in range(n):
        steps += 1
    return steps

def nested(n):
    steps = 0
    for i in range(n):
        for j in range(n):
            steps += 1
    return steps

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

n = 100
print("One pass:", one_pass(n))
print("Nested:", nested(n))
print("Halving:", halving(n))

Exercise

A program visits every pair of items in a list. Which label fits its growth?

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