Free Complexity lessonsComplexity · Stage 1 · Growth in practice · Step 2

Only the biggest term matters

Name an algorithm's growth by its fastest-growing part. About 7 minutes.

Drop constants and small terms

Code that does 3n² + 5n + 7 steps is called O(n²). The 3 doesn't change how the work grows, and 5n and 7 are tiny next to n² once n is large.

Compare a big salary to loose change: when someone earns a million a year, a few coins in their pocket don't change the picture.

3n² + 5n + 7: is O(n²).

The growth ladder · terms = [n, n^2, log n]

log n

n log n

n²

n³

2ⁿ

term

highest: n

First term, n. Find its rung on the ladder.

Move 1 of 4

The growth ladder

From slowest-growing to fastest: 1, log n, n, n log n, n², n³, 2ⁿ. Think of it as a ladder. A cost's Big-O name is the highest rung any of its parts reaches, because the top rung eventually drowns out everything below it. So when you read a cost like n² plus n plus log n, just name the top rung.

2ⁿ: outgrows every power of n.

In code

order = ["1", "log n", "n", "n log n",
         "n^2", "n^3", "2^n"]
return max(terms, key=order.index)

Quick check

A program does n log n + n² + 1,000n steps. What is its Big-O name?

AO(n²)
BO(n)
CO(n log n)

Show the answer

O(n²). n² is the highest rung; the other parts become small as n grows.

Your problem

Name the growth

You get the parts of an algorithm's cost as growth names, each one of "1", "log n", "n", "n log n", "n^2", "n^3" or "2^n". Return the Big-O name of the whole cost: the part that grows fastest.

Example

terms = ["n", "n^2", "log n"] → "n^2"

1 ≤ terms ≤ 20

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.