What common Python operations cost

Complexity analysis Junior Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

Which container answers this faster? What does this print?

Python 3.13

import timeit
xs = list(range(100_000))
ss = set(xs)
t_list = timeit.timeit(lambda: 99_999 in xs, number=50)
t_set = timeit.timeit(lambda: 99_999 in ss, number=50)
print(t_set < t_list)

OptionsTrueFalseIt depends on the item's value

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A True

Right: the set checks one bucket; the list scans 100,000 items.

A hash lookup does constant work, while the list has to compare against every earlier item first.

Why not the others?

B False. List membership is a linear scan, so it is far slower for an item at the end.
C It depends on the item's value. For an item near the end of the list, the scan is always long.

30-second answer

O(1) on average: list index, append and pop from the end; dict and set lookup, insert and delete; deque append and pop at both ends. O(n): x in list, list.insert(0, x), list.pop(0), slicing, list.index, copying, sum, min, max, and building a string with += in a loop. Sorting is O(n log n).

Practise saying it · 45 s. No recording, just a timer

Name the cost of the Python operations you use.

Say your answer out loud, then check which of these points you covered:

O(1): index, append, dict/set lookup
O(n): in list, pop(0), slicing
Sort O(n log n)

Deep dive

len() is O(1) for lists, dicts, sets and strings: the length is stored.

heapq.heappush and heappop are O(log n); heapify is O(n).

str.join is O(total length), which is why it beats repeated +=.

Operation	list	dict or set	deque
Index or lookup	O(1)	O(1) average	O(n) in the middle
Add at end	O(1) amortised	O(1) average	O(1)
Add or remove at front	O(n)	n/a	O(1)
x in container	O(n)	O(1) average	O(n)

Common mistakes

Using a list as a queue with pop(0).
Checking membership in a list inside a loop.

Senior take & follow-ups

Quote two or three of these costs while you code; it shows you are counting as you go.

Follow-up questions

Think of your answer first, then open the hint.

Is dict lookup ever O(n)?
Show hint
In the worst case with many colliding hashes, yes; with ordinary keys it is O(1) on average.
What does list(set(xs)) cost?
Show hint
O(n) on average, and the order is not preserved.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.