C DSA Big O Notation

What is Big O?

Big O describes how the work an algorithm does grows when the amount of data grows.

• The amount of data is called n. For example, the number of items in an array.
• Big O is written with a big letter O, like O(n). You say it like this: "Big O of n".
• Big O does not care about exact seconds. It cares about the shape of the growth: what happens when n gets 10 or 1,000 times bigger?

Count the Steps

In the Searching chapter, binary search was much faster than linear search. Let's count exactly how many checks each one needs in the worst case.

This program does not search anything. It only counts the steps for different sizes of n:

#include <stdio.h>

int main() {
  int sizes[] = {10, 100, 1000, 1000000};

  for (int i = 0; i < 4; i++) {
    int n = sizes[i];

    // Linear search: check every item
    int linearSteps = n;

    // Binary search: cut the items in half until none are left
    int binarySteps = 0;
    int items = n;
    while (items > 0) {
      items = items / 2;
      binarySteps++;
    }

    printf("n = %d: linear = %d steps, binary = %d steps\n", n, linearSteps, binarySteps);
  }

  return 0;
}

n = 10: linear = 10 steps, binary = 4 steps
n = 100: linear = 100 steps, binary = 7 steps
n = 1000: linear = 1000 steps, binary = 10 steps
n = 1000000: linear = 1000000 steps, binary = 20 steps

• Linear search grows at the same speed as n. When n gets 1,000 times bigger, the steps get 1,000 times bigger. We write this as O(n).
• Binary search grows very slowly. When n doubles, it needs only one more step. We write this as O(log n).

"log n" (logarithm) sounds like hard math, but here it just means: "how many times can you cut n in half?"

The Most Common Big O Values

Here are the Big O values you will see most often, from fastest to slowest:

Look at the difference! With 1,000 items, an O(n2) algorithm can need a million steps, while an O(log n) algorithm needs about 10.

Spot the Big O in Your Code

You can often find the Big O just by looking at the loops.

O(1): No Loop

The same number of steps, no matter how big the array is. This is called constant time:

int first = numbers[0];

O(n): One Loop

The loop runs once for every item. This is called linear time:

for (int i = 0; i < n; i++) {
  printf("%d\n", numbers[i]);
}

O(n²): A Loop Inside a Loop

For every item, the inner loop runs through all items again. That is n × n steps, and it is called quadratic time:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    printf("%d %d\n", numbers[i], numbers[j]);
  }
}

O(log n): Cut in Half

The work is cut in half at every step. This is called logarithmic time:

while (n > 0) {
  n = n / 2;
}

Cheat Sheet: This Section in Big O

Here is everything you have learned in this section, with its Big O:

Summary

• Big O describes how the number of steps grows when the data (n) grows.
• From fast to slow: O(1), O(log n), O(n), O(n log n), O(n2).
• Look at the loops: one loop is often O(n), a loop inside a loop is often O(n2).

Well Done!

You have built stacks, queues, linked lists and trees from scratch in C. You can search and sort, and you know how to measure how fast an algorithm is. That is a great start in DSA!