Big O Notation

Here’s a problem every learner hits. You write code that works fine on your laptop with 10 items. Then real users show up with a million items and your program crawls. You had no way to see that coming.

So how do you spot a slow program before it ever runs on big data? You look at how its work grows as the input grows. The tool for describing that growth is called Big O notation, and that’s what we’ll learn here.

📚 What is Big O Notation?

Big O notation is a way to describe how the running time or memory of a program grows as the input gets bigger.

The key word there is grows. We don’t care about the exact seconds. We care about the shape of the growth. Like, if you double the input, does the work stay the same, double, or explode?

Here’s the thing. Big O ignores small details on purpose:

• It ignores constants. So work that takes 2n steps and work that takes 100n steps are both just O(n).
• It ignores small terms. So n² + n becomes just O(n²), because the biggest part takes over when n is large.
• It focuses on the worst case, the slowest the program can get for an input of that size.

We write n for the size of the input. So n is the number of items in your list, the number of users, the number of rows. Whatever you are working on.

🏫 A Real-World Analogy

Picture a big phone book. Inside it, you want to find one person.

• Looking up one page you already know is instant. Page 200 is page 200. The book could have a thousand pages or a million pages. Jumping straight to a known page takes the same effort. That’s constant time.
• Reading the whole book front to back to find a name takes longer as the book gets thicker. Double the pages and you read twice as long. That’s linear time.
• Searching by splitting is the clever middle. You open the middle, see if your name is before or after, then throw away half the book. You repeat on what’s left. Even a giant book gets found in just a handful of steps. That’s logarithmic time.

Keep this phone book in mind. Every Big O class below is just one of these reading habits.

📈 The Common Big O Classes

Let’s walk through the classes you’ll meet most often. We’ll go from fastest to slowest. For each one, think back to the phone book.

O(1) — Constant time

The work stays the same no matter how big the input is. Doesn’t matter if you have 10 items or 10 million. It takes the same effort.

Reading one array element by its index is the classic example. arr[5] is just as fast in a tiny array as in a huge one. That’s the known page in the phone book.

O(log n) — Logarithmic time

The work grows slowly. Every step throws away half the remaining input, so you reach the answer in just a few steps even for huge inputs.

Binary search is the famous example. Searching a list of a billion sorted items takes only about thirty steps. That’s the split-the-book habit.

O(n) — Linear time

The work grows in step with the input. Double the items and you double the work. Simple and fair.

Looking at every item once, like adding up all numbers in a list, is O(n). That’s reading the whole book front to back.

O(n log n) — Linearithmic time

A little slower than linear, but still very usable. You do an O(n) pass, but each part also costs a log n step.

The good sorting algorithms, like merge sort, run in O(n log n). When someone says “sort the data,” this is usually the cost.

O(n²) — Quadratic time

The work grows with the square of the input. Double the items and the work goes up four times. This gets slow fast.

This shows up when you have a loop inside a loop, comparing every item with every other item. Fine for small data. Painful for big data.

O(2^n) — Exponential time

The work doubles every time you add one item to the input. This explodes almost immediately. Even 50 items can be hopeless.

Trying every possible combination, like a brute-force solution to some puzzle problems, lands here. You want to avoid this whenever you can.

🔢 From Fastest to Slowest

Here’s the whole family in one table, fastest at the top. Keep this near you while you learn.

The big jump to notice is between O(n²) and the faster classes above it. If you can turn an O(n²) solution into O(n log n) or O(n), you usually should.

⌨️ Seeing It in Code

Words are nice, but code makes it click. Let’s write three tiny functions, one each for O(1), O(n), and O(n²), and watch how the number of steps changes.

Here’s the plan for each function:

• constant_time returns the first item. It does one step, so it’s O(1).
• linear_time adds up every item once. It does n steps, so it’s O(n).
• quadratic_time makes a pair from every item with every other item. It does n times n steps, so it’s O(n²).

We’ll run all three on the same small list and print how many basic steps each one did.

#include <stdio.h>

// O(1): one step, ignores the size of the array
int constantTime(int *arr, int n) {
    int first = arr[0]; // always just one read
    (void)first;        // we only care that it is one step
    return 1;
}

// O(n): one step per element
int linearTime(int *arr, int n) {
    int steps = 0;
    for (int i = 0; i < n; i++) {
        steps++; // count one step per element
    }
    return steps;
}

// O(n^2): a loop inside a loop, n * n steps
int quadraticTime(int *arr, int n) {
    int steps = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            steps++; // count one step per pair
        }
    }
    return steps;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = 5;

    printf("O(1) steps: %d\n", constantTime(arr, n));
    printf("O(n) steps: %d\n", linearTime(arr, n));
    printf("O(n^2) steps: %d\n", quadraticTime(arr, n));

    return 0;
}

O(1) steps: 1
O(n) steps: 5
O(n^2) steps: 25

#include <iostream>
using namespace std;

// O(1): one step, ignores the size of the array
int constantTime(int arr[], int n) {
    int first = arr[0]; // always just one read
    (void)first;        // we only care that it is one step
    return 1;
}

// O(n): one step per element
int linearTime(int arr[], int n) {
    int steps = 0;
    for (int i = 0; i < n; i++) {
        steps++; // count one step per element
    }
    return steps;
}

// O(n^2): a loop inside a loop, n * n steps
int quadraticTime(int arr[], int n) {
    int steps = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            steps++; // count one step per pair
        }
    }
    return steps;
}

int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = 5;

    cout << "O(1) steps: " << constantTime(arr, n) << endl;
    cout << "O(n) steps: " << linearTime(arr, n) << endl;
    cout << "O(n^2) steps: " << quadraticTime(arr, n) << endl;

    return 0;
}

O(1) steps: 1
O(n) steps: 5
O(n^2) steps: 25

public class BigO {
    // O(1): one step, ignores the size of the array
    static int constantTime(int[] arr) {
        int first = arr[0]; // always just one read
        return 1;           // we only care that it is one step
    }

    // O(n): one step per element
    static int linearTime(int[] arr) {
        int steps = 0;
        for (int i = 0; i < arr.length; i++) {
            steps++; // count one step per element
        }
        return steps;
    }

    // O(n^2): a loop inside a loop, n * n steps
    static int quadraticTime(int[] arr) {
        int steps = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                steps++; // count one step per pair
            }
        }
        return steps;
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};

        System.out.println("O(1) steps: " + constantTime(arr));
        System.out.println("O(n) steps: " + linearTime(arr));
        System.out.println("O(n^2) steps: " + quadraticTime(arr));
    }
}

O(1) steps: 1
O(n) steps: 5
O(n^2) steps: 25

# O(1): one step, ignores the size of the list
def constant_time(arr):
    return arr[0]  # always just one read

# O(n): one step per element
def linear_time(arr):
    steps = 0
    total = 0
    for value in arr:
        total += value
        steps += 1  # count one step per element
    return steps

# O(n^2): a loop inside a loop, n * n steps
def quadratic_time(arr):
    steps = 0
    for i in arr:
        for j in arr:
            steps += 1  # count one step per pair
    return steps

def main():
    arr = [10, 20, 30, 40, 50]
    print("O(1) steps:", 1)
    print("O(n) steps:", linear_time(arr))
    print("O(n^2) steps:", quadratic_time(arr))

if __name__ == "__main__":
    main()

O(1) steps: 1
O(n) steps: 5
O(n^2) steps: 25

// O(1): one step, ignores the size of the array
function constantTime(arr) {
    return arr[0]; // always just one read
}

// O(n): one step per element
function linearTime(arr) {
    let steps = 0;
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
        steps++; // count one step per element
    }
    return steps;
}

// O(n^2): a loop inside a loop, n * n steps
function quadraticTime(arr) {
    let steps = 0;
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            steps++; // count one step per pair
        }
    }
    return steps;
}

function main() {
    const arr = [10, 20, 30, 40, 50];
    console.log("O(1) steps:", 1);
    console.log("O(n) steps:", linearTime(arr));
    console.log("O(n^2) steps:", quadraticTime(arr));
}
main();

O(1) steps: 1
O(n) steps: 5
O(n^2) steps: 25

Look at the numbers for a list of 5 items. O(1) did 1 step. O(n) did 5. O(n²) did 25. Now imagine the list grows to 1,000 items. O(1) still does 1 step. O(n) does 1,000. O(n²) does a million. That gap is the whole story of Big O.

⚠️ Common Mistakes and Misconceptions

A few ideas trip up almost everyone at the start. Let’s clear them out:

• Thinking Big O is about seconds. It’s not. It’s about how the work grows. A fast computer doesn’t change the O(n²) shape into O(n).
• Keeping the constants. Writing O(2n) or O(5n) misses the point. We drop constants, so it’s just O(n).
• Keeping the small terms. For O(n² + n), the n part barely matters once n is large. So we just write O(n²).
• Assuming smaller code is faster. A short function with a nested loop can be O(n²). Lines of code do not equal Big O.
• Mixing O(n²) with O(2^n). They look alike but grow at completely different speeds. The exponential one is far, far worse.

🧩 What You’ve Learned

You can now look at a piece of code and get a feel for how it will behave on big data. Here’s what you’ve picked up.

• ✅ Big O notation describes how running time or memory grows as the input n gets bigger.
• ✅ Big O drops constants and small terms and focuses on the worst-case growth shape.
• ✅ The common classes, fastest to slowest, are O(1), O(log n), O(n), O(n log n), O(n²), O(2^n).
• ✅ O(1) is a known phone-book page, O(n) is reading the whole book, O(log n) is splitting it in half each step.
• ✅ Counting nested loops over the input is a quick way to guess the Big O.
• ✅ Turning an O(n²) solution into O(n log n) or O(n) is usually a big win on large inputs.

🚀 What’s Next?

You’ve got the language of growth. Now go deeper into measuring and comparing algorithms.

• Time Complexity explains how to work out the running time of an algorithm step by step.
• Big O Cheat Sheet is a quick reference for the complexity of common operations.
• How to Analyze Algorithms walks you through reading code and figuring out its Big O.

Try guessing the Big O of every loop you write from now on, and this notation will quickly become second nature.