beginnerintermediateadvanced

Algorithms · Big-O

Big-O and Complexity Analysis

How to name the cost of an algorithm, and the Python-specific facts that decide it

Worst case, by conventiongrowth, not a stopwatch reading
Nested multipliessequential adds — do not confuse them
Hashing is O(1)dict/set beat list for membership checks
+= in a loop is O(n²)use ''.join() instead

1.Common complexity classes, in order

From fastest-growing-slowest to slowest-growing-fastest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!). Each is dramatically worse than the one before it as n grows.

Key features

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!), in order from fastest to slowest
O(log n) usually comes from repeatedly halving a search space (binary search)
O(n log n) is the best achievable for comparison-based sorting
O(2ⁿ) and O(n!) are usually only acceptable for very small n (roughly n ≤ 20–25)

The seven classes, fastest to slowest, with real operation counts at n = 20

The seven classes, fastest to slowest, with real operation counts at n = 20
Class	Name	Ops at n = 20	Typical example
O(1)	Constant	1	dict/set lookup, array index by position
O(log n)	Logarithmic	~4.3	binary search
O(n)	Linear	20	a single loop over the input
O(n log n)	Linearithmic	~86.4	comparison-based sorting (Timsort, merge sort)
O(n²)	Quadratic	400	a loop nested inside a loop
O(2ⁿ)	Exponential	1,048,576	trying every subset of n items
O(n!)	Factorial	2,432,902,008,176,640,000	trying every ordering (permutation) of n items

All seven classes, one picture — note the log scale

Y-axis is log-scaled — without it, every class except O(n!) would be an invisible flat line at the bottom. n=1 is excluded because log2(1)=0, which a log scale cannot plot. Every value computed with math.log2/math.factorial, same as the table above.

Signature

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Memorize the order — O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!) — and always check what an inner loop actually bounds before assuming "nested loop" means O(n²).

2.Analyzing loops (single, nested, sequential)

A single loop over n items is O(n). Two loops one after another (sequential) is still O(n) — they add. A loop inside a loop (nested), each running n times, multiplies to O(n^2).

Key features

Sequential loops (one after another): costs ADD — O(n) + O(n) = O(n)
Nested loops (one inside another): costs MULTIPLY — O(n) * O(n) = O(n^2)
A nested loop's inner bound does not have to be n — a loop nested inside an O(n) loop that itself only runs O(1) or O(log n) times keeps the whole thing at O(n) or O(n log n)

Measured iteration count, same input size, sequential vs nested

Measured iteration count, same input size, sequential vs nested
n	Sequential: O(n) + O(n)	Nested: O(n) * O(n)
2	4	4
4	8	16
8	16	64
16	32	256

Sequential adds; nested multiplies

Measured with count_two_sequential/count_pairs_nested above, not estimated — the nested curve visibly bends upward while sequential stays a straight line.

Loops one after another ADD their costs; a loop nested inside another MULTIPLIES — mixing these up is the single most common complexity-analysis mistake.

3.Membership check (`in`): list O(n) vs dict/set O(1) average

x in some_list scans from the start until it finds x or reaches the end — O(n). x in some_set or x in some_dict uses hashing to jump straight to where x would be — O(1) on average. Same syntax, very different cost.

Key features

x in list_obj is O(n) — worst case, it checks every element
x in set_obj or x in dict_obj is O(1) average — hashing finds the bucket directly
Converting a list to a set costs O(n) once — worth it the moment you check membership more than once

Signature

x in list_obj # O(n) | x in set_obj / dict_obj # O(1) average

`in` on a list is O(n); `in` on a set or dict is O(1) average — if you check membership more than once, convert to a set first.

4.String concatenation in a loop is O(n²)

Building a string with result += piece inside a loop is O(n^2) overall, because strings are immutable — each += copies the ENTIRE string so far into a new, longer one. ''.join(pieces) builds the result once, in O(n).

Key features

Every result += piece allocates a brand-new string and copies everything seen so far into it
Total characters copied across a loop of n pieces is roughly 1+2+...+n = n(n+1)/2 — O(n^2)
''.join(pieces) computes the total length once and copies each piece exactly once — O(n) total

Measured total characters copied by result += piece, across n pieces

Measured total characters copied by result += piece, across n pieces
Pieces (n)	Total characters copied (1+2+...+n)
10	55
100	5,050
1,000	500,500

The copy count curves upward — that bend is O(n²)

Every point is sum(range(1, n + 1)), same formula as the table below — a straight-line (O(n)) cost would be a straight line here; this visibly bends upward, which is what O(n²) looks like.

Never build a string with += inside a loop — the immutability of strings makes it O(n^2). Collect the pieces in a list and call ''.join() once.

5.Dropping constants and lower-order terms

Big-O keeps only the fastest-growing term and drops multipliers: 3n + 5 becomes O(n), and n^2 + n becomes O(n^2). What survives is whichever term dominates once n is large.

Key features

A function that loops over the same input three times, one after another, is still O(n) — 3n simplifies to O(n)
n^2 + n is O(n^2) — the n term becomes irrelevant next to n^2 as n grows
Dropping constants is valid for COMPARING growth rates; it says nothing about which of two O(n) functions is faster in practice

A constant multiplier or a smaller added term never changes the Big-O class — 3n is O(n), and n^2 + n is O(n^2).

6.Time complexity vs space complexity

Time complexity counts how many operations an algorithm does; space complexity counts how much EXTRA memory it uses beyond the input itself. The two are independent — a solution can trade one for the other.

Key features

Space complexity usually excludes the input itself — it counts EXTRA memory the algorithm allocates
A hash set trades O(n) extra space for O(n) time instead of O(n log n) or O(n^2)
Sorting in place (no new list) keeps space at O(1) extra, at the cost of needing O(n log n) time first

Time and space complexity are two separate bills — a faster solution often pays for its speed in extra memory, and that trade is a real design decision, not a side effect.

7.Reading constraints to guess required complexity

A rough rule of thumb: a typical time limit allows about 10^8 simple operations. Divide that by the complexity formula at the stated n, and if the result is comfortably above 1, that complexity is safe to attempt.

Key features

A common rule of thumb: roughly 10^8 simple operations fit in about one second
n ≤ 10^5 with an O(n^2) solution means ~10^10 operations — about 100x over budget
n ≤ 10^5 with an O(n log n) solution means ~1.7 * 10^6 operations — comfortably inside budget

Command

python

OPS_PER_SECOND = 10**8

def fits_time_limit(n, complexity_ops):
    return complexity_ops(n) <= OPS_PER_SECOND

Roughly 10^8 simple operations fit a typical time limit — compute the complexity formula at the stated n and compare, instead of guessing whether an approach is "probably fine".

8.list index/append/pop-from-end: O(1)

Reading items[i], adding with items.append(x), and removing the last item with items.pop() are all O(1) — none of them need to touch any other element.

Command

python

items = [10, 20, 30]
items.append(40)   # O(1)
items[1]            # O(1)
items.pop()         # O(1) — removes and returns the LAST item

Index access, append, and pop-from-the-end are the three O(1) list operations — everything else that touches position 0 or the middle is not.

9.list insert/pop/delete at an arbitrary index: O(n)

Inserting or removing anywhere except the end forces every following element to shift by one position — items.insert(0, x) and items.pop(0) are both O(n), not O(1).

Command

python

items = [10, 20, 30]
items.insert(0, 5)   # O(n) — 10, 20, 30 all shift right by one
items.pop(0)         # O(n) — every remaining item shifts left by one
del items[1]         # O(n) — same shifting cost

Anything that is not at the very end (insert, pop, del at an index) costs O(n) on a list, because everything after it has to shift.

10.sorted() / list.sort(): O(n log n), Timsort

Both sorted() (returns a new list) and list.sort() (sorts in place) run in O(n log n) worst case, using Timsort — a hybrid of merge sort and insertion sort tuned for real-world, partially-ordered data.

Key features

sorted(items) returns a new sorted list; items.sort() sorts in place and returns None
Both are O(n log n) worst case — the best possible for a general comparison-based sort
Timsort is stable: elements that compare equal keep their original relative order
Already partially-sorted input can run faster than O(n log n) in practice — Timsort detects and exploits existing runs

Command

python

sorted([3, 1, 2])          # [1, 2, 3] — new list, O(n log n)
items = [3, 1, 2]
items.sort()                # in place, O(n log n), returns None
sorted(items, key=len)      # sort by a derived value instead of the items themselves

sorted()/list.sort() are both O(n log n) worst case, using Timsort — reach for them instead of writing a manual sort in almost every practical case.

Spotted a mistake on this page? Tell us.

Read Sheet