Big O Notation Explained Simply (Graph + Examples)

Big O notation is the first big hurdle in every data structures and algorithms (DSA) course, and it shows up in almost every coding interview. The good news: the idea behind it is simple. Big O answers one question: when the input gets bigger, how fast does the work grow?

In this guide you'll get the plain-English meaning, a Big O graph, code examples in Python, Java and C++, a live “growth race”, and a memory trick so the order of complexities sticks for good.

What is Big O notation?

Imagine two apps that both search a contact list. With 10 contacts, both feel instant. With 10 million contacts, one still answers instantly and the other freezes. Big O is the tool that predicts this before you run anything.

It doesn't measure seconds, because seconds depend on your laptop. Instead it describes the growth rate: how the number of steps changes as the input size, called n, gets larger. That's why it's also called time complexity.

The Big O graph: common complexities

O(1): constant time

The work is the same no matter how big the input is. Reading items[0] from an array takes one step whether the array has 10 or 10 million elements.

O(log n): logarithmic time

The problem is cut in half at every step. Looking up a word in a dictionary by opening the middle, then the middle of the right half, and so on is O(log n). It's how binary search works, and it's incredibly fast: about 20 steps for a million items.

O(n): linear time

The work grows in step with the input. Checking every item in a list once is O(n).

O(n log n): linearithmic time

The sweet spot for sorting. Efficient sorting algorithms like merge sort split the data in halves (log n levels) and do n work at each level.

O(n²): quadratic time

Usually a loop inside a loop: for each item, look at every other item. Fine for 100 items, painful for 100,000. Simple sorts like bubble sort are O(n²).

O(2ⁿ): exponential time

Every extra input item doubles the work. Trying every possible combination of n items grows like this. Even n = 60 is out of reach for any computer.

How to calculate Big O: 3 simple rules

1. Count the loops over the input. No loop → O(1). One loop → O(n). A loop inside a loop → O(n²). Halving each time → O(log n).
2. Drop the constants. 2n, n + 10 and n/2 are all just O(n). Big O cares about the shape, not the exact count.
3. Keep only the biggest term. n² + n becomes O(n²), because for large n the n² part completely dominates.

def get_first(items):          # O(1): one step, any size
    return items[0]

def contains(items, target):   # O(n): may check every item
    for x in items:
        if x == target:
            return True
    return False

def has_duplicate(items):      # O(n²): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Common Big O mistakes students make

• Counting two separate loops as O(n²). One loop after another is O(n) + O(n) = O(n). Only nested loops multiply.
• Keeping constants. Writing O(2n) isn't wrong, but the convention is O(n).
• Forgetting hidden loops. Built-in operations like searching a list (x in list in Python) loop internally and cost O(n).
• Mixing up time and space. A fast algorithm might use extra memory; analyse both.

What to learn next

Big O is the language you'll use for every other DSA topic. Next, see it in action with binary search (the classic O(log n) algorithm), compare O(n²) vs O(n log n) in our sorting algorithms visualizer, and learn the two most common data structures in stack vs queue.

Frequently asked questions