Complexity of operations: O-notation, counted on built-in types

Base: what O-notation says

Here n is the number of elements in the collection, and the work is the number of element comparisons (for append and insert — reference copies), not time.

A junior-level answer to "what is O(n)": it is how an algorithm's running time grows with the size of the input; constants and lower-order terms are dropped. More strictly: O(f(n)) is an asymptotic upper bound in a chosen cost model: from some n on, the work is at most c·f(n). So a linear function is formally both O(n) and O(n²); a tight bound — grows exactly like f(n) up to a factor — is written Θ(f(n)), and in an interview "O(n)" usually means that. That is correct, and it is usually followed by questions: what is the complexity of specific list and set operations, what "amortized" means, and where a square hides in code that looks linear. The mechanisms below answer them by counting.

How the check works: the elements are objects that count calls to their __eq__ and __lt__. For a scan, binary search and sorting the number of comparisons is the measure of the work. It does not depend on the speed of the machine and matched on CPython 3.11–3.14, but it is an observation of the implementation for these objects, not a contract of the language: other data — coinciding hashes, for example — give a different count. Computing hashes is not counted, and one comparison is not one machine operation: for long strings both hash and == go over the characters (the section "Deeper: the cost of one comparison").

Mechanism 1: lookup — O(n), O(1) and O(log n) in numbers

Output of bench/complexity/basics.py, section 1 (labels translated):

1) lookup: how many comparisons, the element sought is the last one
         n   x in list  x in set  bisect  log2(n)
        10          10         1       3      3.3
       100         100         1       7      6.6
      1000        1000         1      10     10.0
     10000       10000         1      13     13.3
    100000      100000         1      17     16.6
   bisect on the unsorted [5, 1, 4, 2, 3], looking for 1: index 0, while 1 is at position 1 — no error

Three columns — three kinds of growth:

• x in list is O(n). A scan compares the elements one by one, and there are exactly n comparisons when the element sought is the last.
• x in set is O(1) on average. A set computes the hash, goes to the right slot and compares the element with those that have the same hash. For the run's Key the hashes of different values do not coincide, so __eq__ was called once — with ten elements and with a hundred thousand. That is an observation for this set of keys, not a property of sets: below is the same lookup when all elements share one hash.
• bisect is O(log n). Binary search on a sorted list discards half with every comparison. n grew ten thousand times, and there are 14 more comparisons — the column keeps pace with log2(n).

If all elements share one hash — the output of bench/complexity/basics.py, section 6 (labels translated):

6) a set where all elements have the same hash: __eq__ calls
         n  normal hashes  one hash: lookup  one hash: building
        10              1                10                   45
       100              1               105                 5982
      1000              1              1336               605201
     10000              1             11672             57720235
   the same experiment with hash 0 instead of 1, n = 100: lookup — 114
   normal hashes, the one sought is the same object, not an equal one: lookup — 0

With one hash for all, looking up the last element called __eq__ 105 times at a hundred elements and 11,672 times at ten thousand — on the order of n: this is a set's worst case, O(n). There are even more calls than n — so the set compared some elements more than once; the exact number depends even on the hash value itself: with zero instead of one it is 114. Building such a set costs on the order of n²/2 comparisons. And an element found by identity — the same object, not an equal one — calls no __eq__ at all. So "O(1) on average" does not mean "one comparison", and the __eq__ counts themselves are an observation of CPython, not a promise of the language.

bisect is a standard library module, and its condition is written right in the docstring of bisect_left: "return the index where to insert item x in list a, assuming a is sorted". Being sorted is the caller's responsibility: on an unsorted list bisect returns a wrong index without an error — the last line of the run above. That is why the O(log n) of the lookup goes together with the O(n log n) of sorting: binary search pays off when a list is sorted once and searched many times.

One more thing: bisect_left returns an insertion position, not an answer to "is the element there". The 17 comparisons in the table above are only the __lt__ calls up to that position. Whether the element was found is decided by a separate check: the position is inside the list and the element there equals the one sought — i < len(a) and a[i] == x. The output of bench/complexity/basics.py, section 7 (labels translated):

7) bisect: an insertion position is not yet "found" — a check after it is needed
   looking for  199998 in 0, 2, 4, …, 199998: position  99999, __lt__ — 17, __eq__ — 1, found: True
   looking for   77777 in 0, 2, 4, …, 199998: position  38889, __lt__ — 17, __eq__ — 1, found: False
   looking for  200001 in 0, 2, 4, …, 199998: position 100000, __lt__ — 16, __eq__ — 0, found: False

For 77,777, which is not in the list, bisect_left still returned a position — 77,778 stands there; without the equality check it would look like a hit. For 200,001 the position equals the length of the list, and there is nothing to compare with — hence the bounds check.

The same in a short example that can be copied. The full file bench/complexity/find.py:

import bisect
import sys
 
print("PY", sys.version.split()[0])
 
 
def contains(a, x):
    i = bisect.bisect_left(a, x)
    return i < len(a) and a[i] == x
 
 
a = [2, 4, 6, 8]
for x in (6, 5, 9):
    print(f"x = {x}: bisect_left -> {bisect.bisect_left(a, x)}, contains -> {contains(a, x)}")

Run it with python3.13 bench/complexity/find.py; the output on CPython 3.13.7 (the same on 3.11, 3.12 and 3.14 except for the version line), exactly as printed:

PY 3.13.7
x = 6: bisect_left -> 2, contains -> True
x = 5: bisect_left -> 2, contains -> False
x = 9: bisect_left -> 4, contains -> False

For 6 and for 5 the position is the same — 2; only the equality check tells them apart.

Mechanism 2: append — amortized O(1)

A list keeps references to its elements in one block of memory. When the space runs out, a bigger block is needed, and all the references may have to be copied — that is O(n). If that happened on every append, n appends would cost O(n²). So CPython allocates memory with a reserve; the run catches every reallocation by a change in sys.getsizeof — the output of bench/complexity/basics.py, section 2 (labels translated):

2) append: how many times the list reallocated memory
   first capacities (slots for elements): [4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128]
      1000 appends — reallocations: 28
     10000 appends — reallocations: 47
    100000 appends — reallocations: 66

The series of capacities matches the comment in the CPython sources — 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... — and the same comment says why it is like that: the reserve "is enough to give linear-time amortized behavior over a long sequence of appends()". The reserve grows with the size, so a hundred thousand append calls took 66 reallocations, not a hundred thousand.

This is what amortized O(1) means: an individual append is occasionally expensive — it may copy the whole list — but n appends cost O(n) in total, that is O(1) on average per call. The answer "append is O(1)" is right, but with the expected caveat: in the worst case an individual call is O(n).

Mechanism 3: growth of time — the same, by the clock

O-notation predicts how many times the time grows if n grows tenfold: O(1) — roughly not at all, O(n) — roughly tenfold. A measurement at three sizes — the output of bench/complexity/cost.py (CPython 3.13.7; labels translated):

ns per operation, medians of 7 rounds
   operation                     1000       10000      100000     ×10    ×100
   list.append                   35.1        26.3        28.4     0.8     0.8
   list.insert(0, x)            308.2      2242.9     19988.0     7.3    64.9
   x in list                   5332.6     52136.7    643060.2     9.8   120.6
   x in set                      25.4        27.2        26.2     1.1     1.0
   sorted(), per element        106.7       127.0       220.3     1.2     2.1

• append and x in set — the time per operation does not grow: O(1) (amortized and average; x in set here is on integers without collisions).
• insert(0, x) and x in list — grow almost tenfold for each ×10: O(n). insert(0, x) shifts all the elements, x in list scans them.
• sorted() per element grows slowly — 1.2 times per ×10: that is the log n factor of O(n log n).

The numbers do not fit the prediction exactly. For insert(0, x) it is 7.3 instead of 10, but that is a property of the measurement: over a thousand inserts the list grows to n + 1,000, so the average lengths are 1,500 and 10,500, whose ratio is about 7. For sorted() it is 2.1 at ×100 instead of the 1.7 the logarithm suggests. O-notation drops fixed costs and says nothing about what happens in the hardware; it describes the shape of growth, not the exact time. That is why in an interview you say "grows linearly", not "ten times slower".

Mechanism 4: the hidden square

The most common "estimate the complexity" question is about code where the loop is not visible. [x for x in a if x in b] looks like one pass over a. But if b is a list, each x in b is a pass too. The output of bench/complexity/basics.py, section 3 (labels translated):

3) the hidden square: [x for x in a if x in b], no common elements
         n     b is a list    b is a set
       100         10000               0
      1000       1000000               0

n grew tenfold — there are a hundred times more comparisons: that is O(n²). With a set b there are no __eq__ calls at all: the hashes of the elements of a match no hash in the set, and __eq__ is called only when hashes match. Building the set is O(n) on average, a lookup is O(1) on average per element, O(n) in total; with coinciding hashes both bounds are worse (section 6 above).

Where else a square hides: lst.remove(x) or lst.index(x) in a loop over another collection — for x in to_delete: lst.remove(x) — lst.insert(0, x) in a loop, x in lst for selecting unique items. There is one rule: multiply the number of loop iterations by the cost of the operation inside it.

Deeper: sorting and n − 1 comparisons

Output of bench/complexity/basics.py, section 4 (labels translated):

4) sorted(): how many comparisons
         n     random   lg(n!)  n·log2(n)           sorted  reversed
      1000       8655     8529       9966              999       999
     10000     120184   118458     132877             9999      9999
    100000    1531824  1516704    1660964            99999     99999

On random data there are about n·log2(n) comparisons — that is O(n log n). The lg(n!) column is the theoretical minimum: no comparison sort can do with fewer on average. On 3.13 CPython's sort is 1–1.5% above it.

On already sorted and strictly descending data the run gave exactly n − 1 comparisons, O(n). That is an observation on such an ordered input and this implementation, not a promise of the language; the way the sort is built explains it: CPython's sort looks for ready-made ordered runs in the input, reverses the descending ones and merges them; if the whole input is one such run, one pass over it is enough. So the answer "sorted() is O(n log n)" holds for the worst and the average case, while the best one is O(n).

Deeper: the cost of one comparison

The whole lesson counts comparisons as if each one cost the same. For integers that is close to the truth, for strings it is not: the hash and the equality check go over the characters. The output of bench/complexity/strkeys.py (CPython 3.13.7; labels translated):

string keys: ns per operation, medians of 7 rounds
   operation                           10        1000      100000
   hash(a new string)                35.3       431.8     29768.6
   hash(the same string)             34.6        34.6        30.1
   a == b, different objects         21.3        36.0      2567.6

The hash of a new string of a hundred thousand characters is about 30 µs, of ten characters — 35 ns; comparing two equal but different strings also grows with the length. Hashing the same string again is cheap at any length: the string remembers its hash (the hash field in Include/cpython/unicodeobject.h:101, CPython 3.13.7). So "a set lookup is O(1)" is O(1) in the number of elements, while the cost of one check depends on the key: a new long string has to be hashed, and an equal but different one compared character by character.

How to answer in an interview

Short answer: O-notation describes how the work grows with the input; strictly it is an upper bound. x in list, insert(0, x), remove are O(n); x in set, d[key] are O(1) on average and O(n) in the worst case, when hashes coincide; append is amortized O(1); bisect is O(log n); sorted() is O(n log n) in the average and worst case. The complexity of code is the number of iterations times the cost of the operation inside.

That is enough for a correct answer. What follows is what you add if the interviewer digs.

If the interviewer digs deeper

On "estimate [x for x in a if x in b]". "If b is a list, O(n·m): each in scans b. At a thousand elements I got a million comparisons. Make b a set and it becomes O(n + m)."

On "why is append O(1) if the list is sometimes copied". "It grows with a reserve proportional to its size. A hundred thousand appends took 66 reallocations. Expensive calls are rare; in total it is O(n), that is O(1) on average. That is amortized complexity."

On "what is the complexity of sorted()". "O(n log n) in the average and worst case. On already sorted data it is O(n): I got exactly n − 1 comparisons, CPython's sort finds ready-made runs."

On "why is binary search fast". "Each comparison discards half: on a hundred thousand elements, 17 comparisons instead of a hundred thousand. But the list has to be sorted, and sorting is O(n log n), so it pays off with many lookups. And bisect_left gives an insertion position — whether the element was found I check separately: i < len(a) and a[i] == x."

On "is x in set one comparison?" "O(1) on average, but not one comparison by definition. In my run keys without collisions did give one, but when all hundred elements shared one hash, a lookup called __eq__ 105 times — the worst case, O(n). That is a CPython counter, not a language guarantee."

Next they ask

5) a dict where all keys have the same hash: comparisons to look up the last key
   n =    10: normal hashes — 1, one hash for all — 10
   n =   100: normal hashes — 1, one hash for all — 100
   n =  1000: normal hashes — 1, one hash for all — 1000

Common misconceptions

Version history

Practice

Two problems. Answer first, then check against the real output: in both, the correct answer is taken from a run of the script rather than assigned.

n = 100
count = 0
for i in range(n):
  for j in range(i + 1, n):
      count += 1
print(count)

4950

10000

5000

100

Check yourself

How it was measured

The numbers of this lesson come from these scripts. Each one opens right from here — together with the record of its run: what it ran on, what came out and with what spread.

Comparison counts — CPython 3.11.15, 3.12.3, 3.13.7 and 3.14.7; time measurements — 3.13.7 and 3.14.7 on one machine with two cores. Sections 6–7 of bench/complexity/basics.py, bench/complexity/strkeys.py and bench/complexity/find.py were added and run on 14.10.2026 on linux/x86_64. Contracts and quotes were checked on 14.10.2026. The lesson did not run Python 3.15 (released on 9 October 2026).

• bench/complexity/basics.py
• bench/complexity/cost.py
• bench/complexity/strkeys.py
• bench/complexity/find.py
• bench/complexity/practice.py