Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 225 · Analyzing Algorithms

Big O Notation

Understand Big O notation from scratch. Compare growth rates from O(1) to O(n!), learn to drop constants, meet Omega and Theta, and count real operations.

Suppose two programmers solve the same problem. One program finishes in a blink on your test data, the other takes a second. Which one is better? You cannot tell yet, because the real question is: what happens when the input is a thousand times bigger? If the first one slows down a million-fold and the second only a thousand-fold, the "slow" one wins the moment real data arrives.

Big O notation is the standard language for answering that question. It describes how the amount of work an algorithm does grows as the input grows, ignoring details that don't matter at scale: your computer's speed, the programming language, and small constant factors. It is the single most important tool in this tutorial, and every lesson from here on ends with a Big O summary.

Counting steps, not seconds

Seconds depend on the machine. Steps don't. So we count basic operations (comparisons, additions, assignments) as a function of the input size n. Take a function that finds the largest item:

Python
def largest(items):
    best = items[0]            # 1 step
    for x in items:            # n iterations
        if x > best:           # 1 comparison per iteration
            best = x           # at most 1 assignment per iteration
    return best                # 1 step

For n items the work is roughly n comparisons plus a few extra steps. Whether it is n + 3 or 2n + 1 depends on how you count, and neither matters to the big picture: double the input and the work doubles. We say the function is O(n), read "order n" or "linear time".

What Big O keeps and what it drops

Two rules turn a precise step count into a Big O class.

Rule 1: drop constant factors. 5n and n both grow in a straight line. 100n is slower than n by a fixed factor, but both double when n doubles. Both are O(n).

Rule 2: keep only the fastest-growing term. In n² + 50n + 1000, when n is large, n² swamps the rest. At n = 1000 the terms are 1,000,000, 50,000 and 1,000. The class is O(n²).

Python Why we keep only the biggest term

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

As n grows, the n² term makes up nearly all the work. That is why we say the algorithm is O(n²) and stop worrying about the 50n and the 1000.

Dropping constants does not mean they never matter. A 100n algorithm really is slower than an n algorithm. Big O answers a different question: how does the cost scale? When two algorithms have the same Big O, constants and cache behaviour (see Memory and Data Layout) decide the winner.

The common growth rates

These are the classes you will meet, from fastest to slowest growth.

Big O Name Everyday example
O(1) constant read a[i], push onto a stack
O(log n) logarithmic binary search, halving a range
O(n) linear scan a list once
O(n log n) linearithmic good sorting (merge sort, sorted)
O(n²) quadratic compare every pair, simple nested loops
O(n³) cubic three nested loops, naive matrix multiply
O(2ⁿ) exponential all subsets, naive Fibonacci
O(n!) factorial all orderings (permutations)

Here is what each looks like in code, with a counter so you can see the steps.

Python One function per growth rate

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the rows. Going from n = 10 to n = 1000 (100 times bigger), the constant column does not move, the logarithmic column grows from 3 to 9, the linear one grows 100 times, n log n grows about 300 times, and the quadratic one grows 10,000 times. Picture it:

TEXT
steps
  ^
  |                                        n^2
  |                                    .
  |                                .
  |                            .          n log n
  |                        .         . . . 
  |                    .       . .          n
  |                .     . .  .  .  .  .  .  .
  |            .   . .  . .  .  . .  .  .  .   log n
  |        . . . . . . . . . . . . . . . . . .  . .
  |  ......................................... 1
  +-------------------------------------------------> n

Reading the classes

  • O(1): the cost does not depend on n. Indexing a list or looking up a dict key is O(1) on average.
  • O(log n): the cost grows by one step each time the input doubles. A million items need about 20 steps, a billion about 30. This is the signature of repeated halving, as in binary search.
  • O(n): touch every item a constant number of times.
  • O(n log n): the cost of efficient comparison sorting. See merge sort.
  • O(n²): the signature of a loop inside a loop over the same data. Fine for a few thousand items, painful for a million.
  • O(2ⁿ) and O(n!): every extra item doubles (or multiplies) the work. Only usable for tiny n such as 20 or 10.

Counting real work for n = 10, 100, 1,000

Numbers make the gap sink in. For a single run of each class:

Python How fast each class grows

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At n = 1000 an O(n²) algorithm does a million steps and an O(n³) algorithm a billion, while an O(n log n) one does about ten thousand. An exponential algorithm at n = 30 already needs over a billion steps, and 15! is over a trillion. No amount of faster hardware rescues the bad classes; only a better algorithm does.

Finding the Big O of code

Apply a few reading rules to code:

  1. Sequential steps add: a loop of n followed by a loop of n is n + n, which is O(n).
  2. Nested loops multiply: a loop of n containing a loop of n is n · n, which is O(n²).
  3. Different inputs, different letters: a loop over list a then list b is O(a + b); nested it is O(a · b). Do not call both n unless they are.
  4. Halving gives log: a loop that halves its variable runs about log₂ n times.
  5. Take the worst term: O(n² + n) is O(n²).
Python Add, multiply, and two different inputs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The next lesson, Analyzing Loops and Code, practises these rules on many more shapes.

The formal idea (optional but useful)

Informally, f(n) is O(g(n)) if g grows at least as fast as f, once n is large enough and up to a constant factor. Formally: there are constants c > 0 and n₀ such that

TEXT
f(n) <= c * g(n)    for all n >= n0

So 3n + 10 is O(n): pick c = 4 and n₀ = 10, and 3n + 10 <= 4n whenever n >= 10. You can check a witness by brute force:

Python Checking a Big O witness (c and n0)

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second line fails because at n = 1, 2, ..., 9 the inequality does not hold yet, which is exactly why n₀ exists. The third fails: for n above 1000 the square overtakes 1000n, and any constant would eventually be beaten.

Big O, Omega and Theta

Big O is an upper bound, "at most this fast-growing". Two companions complete the picture:

Symbol Meaning Informal reading
O(g) grows no faster than g upper bound (at most)
Ω(g) grows at least as fast as g lower bound (at least)
Θ(g) both O(g) and Ω(g) tight bound (exactly this rate)

Because O is only an upper bound, "linear search is O(n²)" is technically true but useless. Saying it is Θ(n) in the worst case is precise. In daily use, people say "O(n)" when they mean the tight bound, and so will we, but remember the distinction when you read a formal text. Best, worst and average case is about something different: which input you analyse, and it combines with O, Ω and Θ rather than replacing them.

What Big O does not tell you

  • Constants and small inputs. For tiny n, an O(n²) insertion sort can beat an O(n log n) sort. Real libraries mix both (Timsort).
  • Memory behaviour. Cache effects can make one O(n) loop several times faster than another.
  • Which case you analyzed. Always say whether you mean worst, average or amortized cost (amortized analysis).
  • Space. Time is only half of it; space complexity is next to it.

Common mistakes

  • Saying O(2n) or O(n + 5). Write O(n).
  • Treating all loops as O(n). A loop that halves is O(log n); a nested loop over different sizes is O(a · b).
  • Forgetting hidden costs. x in some_list, slicing and list.insert(0, x) are O(n) operations hiding inside one line.
  • Mixing up O(log n) bases. Base 2, 10 or e differ only by a constant, so we write O(log n) for all.
  • Calling a lookup O(1) without saying "average". Hash table lookups are O(1) on average, and O(n) in a pathological worst case.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is the Big O class of an algorithm that takes 5n + 30 steps?

    Drop constant factors and lower-order terms, so 5n + 30 becomes O(n).
  2. 2. A function has two nested loops, each running n times. Another function runs one loop of n and then another loop of n. Which pair of classes is correct?

    Nested loops multiply their counts (n times n), while sequential loops add (n plus n, which is O(n)).
  3. 3. About how many halvings does it take to reduce 1,000,000 items to 1?

    Since 2 to the power 20 is about a million, repeated halving takes roughly 20 steps. This is why O(log n) is so fast.
  4. 4. Which statement about O, Omega and Theta is correct?

    O bounds growth from above, Omega from below, and Theta from both sides.
  5. 5. For which problem size is an O(2^n) algorithm still practical?

    At n = 20 there are about a million steps, but at n = 100 there are more steps than can ever be run. Exponential algorithms need small inputs.

Summary

  • Big O describes how the work of an algorithm grows with input size, ignoring machine and constants.
  • Drop constant factors and keep only the fastest-growing term: 3n² + 5n + 9 is O(n²).
  • The ladder from best to worst: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!).
  • Sequential code adds, nested loops multiply, halving gives log n.
  • Formally, f is O(g) if f(n) is at most c times g(n) for all n beyond some n₀. Ω is a lower bound and Θ a tight bound.
  • Big O hides constants, cache behaviour and which case you analyze, so use it to compare how algorithms scale, not to predict exact times.

Next: Analyzing Loops and Code, where you will practise reading the Big O of real loops and built-in operations.