Python Time Complexity for Interviews

Where these figures come from

Python now publishes this table itself. The figures below are from Time complexity of operations on built-in types in the official documentation, which replaced the old wiki page, plus the deque and heapq pages for the two types it does not cover. All were read on November 5, 2026, in the Python 3.15.2 documentation.

The table describes CPython and says other implementations may differ. n is the number of elements in the container and k is an index or a repeat count. It also says the costs assume exact built-in types, so a subclass may behave differently.

list

From the list table. The two costs interviewers ask about are the front of the list and the slice.

dict

From the dict table, which calls these average-case times. They assume a hash function robust enough to make collisions uncommon, well-distributed keys, and O(1) hashing and comparing. In the worst case, when every key hashes to the same value, each O(1) below becomes O(n). That is the sentence to have ready when you say "hash lookup."

set

From the set table. The same caveats apply as for dict: these are average-case times, and in the worst case the O(1) operations take O(n).

collections.deque

The table does not cover deque, so this is from the deque documentation, which gives its figures in prose. Use a deque for a queue: its whole purpose is to avoid what list.pop(0) does.

heapq

This is also outside the table, and the heapq documentation states less than people assume. A heap in heapq is a plain list, so reading the smallest item is a list read at index 0.

Since Python 3.14, heapq also has heapify_max, heappush_max and heappop_max. On older versions, push negated values to get a max-heap.

str

From the str table. Strings are immutable, so copying one returns the same object, but every concatenation builds a new one.

For the fix, Python's programming FAQ recommends putting the pieces in a list and calling str.join at the end, and its sequence-types page says that gives a linear runtime cost.

Hidden costs interviewers catch

Each of these looks like a single cheap line, and each comes straight from a row above. They are also how a correct answer quietly becomes too slow.

from collections import deque

# 1. Membership in a list inside a loop: O(n) per check, O(n²) in all.
def first_seen_slow(items):
    seen, out = [], []
    for x in items:
        if x not in seen:          # list: O(n)
            seen.append(x)
            out.append(x)
    return out

def first_seen(items):
    seen, out = set(), []
    for x in items:
        if x not in seen:          # set: O(1) on average
            seen.add(x)
            out.append(x)
    return out

# 2. Using a list as a queue: pop(0) moves every remaining element.
def drain_slow(tasks):
    order = []
    while tasks:
        order.append(tasks.pop(0)) # O(n) per pop
    return order

def drain(tasks):
    queue, order = deque(tasks), []
    while queue:
        order.append(queue.popleft())   # about O(1) per pop
    return order

# 3. Building a string with +=: each step copies what came before.
def join_slow(words):
    out = ""
    for w in words:
        out += w                   # quadratic in the total length
    return out

def join(words):
    return "".join(words)          # linear in the total length

# 4. Slicing in recursion: each call copies the rest of the list.
def total_slow(nums):
    return nums[0] + total_slow(nums[1:]) if nums else 0   # O(n²) time

def total(nums, i=0):
    return nums[i] + total(nums, i + 1) if i < len(nums) else 0   # O(n)

Both versions of the fourth example still use O(n) stack space, and Python's recursion limit will stop either one on a long list, so a loop is better there. Mentioning that before you are asked is a good way to show you know where the cost lives.

How to say it out loud

The habit to build is naming the condition along with the figure: average case for dict and set, amortized for append, and CPython if the interviewer pushes. You can practice saying it in a coding mock interview, and the Big O cheat sheet covers how to derive the rest.

What the docs do not state

These common operations have no figure in the pages above, so they have no row here. If one comes up, reason from the structure and say that is what you are doing.

• heapq.heappush: the docs describe a binary heap but give no cost for a push.
• heapq.nlargest and nsmallest: the docs compare them with sorting and min or max, but give no Big O.
• deque.rotate and membership with in on a deque: no figure given.
• str.join, str.split and str.replace: no row in the table. Only the linear total for join is stated, in prose.