What is the complexity of this code?

Interview QuestionsBy Ashish JangraUpdated 30 August 2026

Four shapes turn linear code quadratic, and interviewers use all of them: in on a list inside a loop, += on a string in a loop, pop(0) used as a queue, and sorted() called inside a loop. Each is cheap once and fatal repeated.

Overview

The pattern

Quadratic code rarely looks quadratic. There is no visible nested loop — instead, an O(n) operation hides inside an O(n) loop, and the cost multiplies.

The reason it survives review and testing is scale. A thousand items finish in milliseconds; a hundred thousand takes minutes. The bug ships because the test data was small.

n	O(n) work	O(n²) work
1,000	1 thousand	1 million — still instant
10,000	10 thousand	100 million — noticeable
100,000	100 thousand	10 billion — minutes
1,000,000	1 million	10¹² — hours

The skill being tested is knowing which innocent-looking operations are O(n), so you can spot them inside a loop.

Dicts, sets & hashingConceptualMedium

Step through it

What to watch

Every individual line here is idiomatic and fine.
The cost comes from the nesting, which is invisible on small input.
Each fix is one line, and each is a different structure.

Say this out loud

"That's O(n²) - the membership test inside the loop is a linear scan. Build a set once before the loop and it's O(n)."

import time from collections import deque def in_set(items, pool): lookup = set(pool) # once, outside the loop return [x for x in items if x in lookup] print("set membership :", in_set(list(range(300)), set(range(300))), "checks")

import time from collections import deque class Buf: # an attribute defeats CPython's def __init__(self): # in-place resize special case self.text = "" def concat(n): b = Buf() for i in range(n): b.text += "x" return b.text print("+= in a loop :", len(concat(2000)), "chars")

import time from collections import deque def join(n): parts = [] for i in range(n): parts.append("x") return "".join(parts) print("str.join :", len(join(2000)), "chars")

import time from collections import deque def queue_list(n): q = list(range(n)) while q: q.pop(0) # shifts everything left print("list.pop(0) :", queue_list(2000))

import time from collections import deque def sort_inside(values): out = [] for _ in range(len(values)): out.append(sorted(values)[0]) # re-sorts every iteration return out print("sort in a loop :", sort_inside(list(range(200, 0, -1)))[:5])

import time from collections import deque def sort_once(values): ordered = sorted(values) return [ordered[0] for _ in range(len(values))] print("sort once :", sort_once(list(range(200, 0, -1)))[:5])

# The running example the prose assumes. items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] words = ["quadratic", " ", "is", " ", "slow"] queue = list(range(6)) data = [3, 1, 4, 1, 5] s = "abcdef" running, seen = [], {} def process(ch): pass def main(): sum(range(1000)) # O(n^2): `in` on a list scans it seen = [] for item in items: if item not in seen: # O(n) scan, every iteration seen.append(item) # O(n): `in` on a set hashes seen = set() for item in items: if item not in seen: # O(1) seen.add(item) print("deduped:", sorted(seen))

# The running example the prose assumes. items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] words = ["quadratic", " ", "is", " ", "slow"] queue = list(range(6)) data = [3, 1, 4, 1, 5] s = "abcdef" running, seen = [], {} def process(ch): pass def main(): sum(range(1000)) # O(n^2): each += builds a whole new string out = "" for word in words: out += word # O(n): one allocation at the end out = "".join(words) print("joined:", repr(out))

queue = list(range(6)) # O(n^2): every element shifts on each pop while queue: item = queue.pop(0) print("drained with pop(0)") # O(n): a deque pops from the left in O(1) from collections import deque queue = deque(range(6)) while queue: item = queue.popleft() print("drained with popleft, queue now:", list(queue))

# The running example the prose assumes. items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] words = ["quadratic", " ", "is", " ", "slow"] queue = list(range(6)) data = [3, 1, 4, 1, 5] s = "abcdef" running, seen = [], {} def process(ch): pass def main(): sum(range(1000)) # O(n^2): max rescans everything each time for x in data: running.append(x) print(max(running)) # O(n): track it incrementally best = float("-inf") for x in data: best = max(best, x) print(best)

# The running example the prose assumes. items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] words = ["quadratic", " ", "is", " ", "slow"] queue = list(range(6)) data = [3, 1, 4, 1, 5] s = "abcdef" running, seen = [], {} def process(ch): pass def main(): sum(range(1000)) # O(n^2): each slice copies the remainder while s: process(s[0]) s = s[1:] # O(n): move an index for i in range(len(s)): process(s[i]) print("walked", len(s), "characters without re-slicing")

Operation	Cost	The O(1) or O(n) alternative
`x in list`	O(n)	`x in set` or `x in dict`
`s += x` in a loop	O(n)	`"".join(parts)`
`lst.pop(0)`	O(n)	`deque.popleft()`
`lst.insert(0, x)`	O(n)	`deque.appendleft()`
`lst.remove(x)`	O(n)	Set, or mark as deleted
`max(lst)` repeatedly	O(n)	Running maximum, or a heap
`s[1:]` repeatedly	O(n)	Index arithmetic
`del lst[0]`	O(n)	`deque`
`lst.index(x)`	O(n)	Dict from value to index
`sorted()` inside a loop	O(n log n)	Sort once outside

Operation

Cost

The O(1) or O(n) alternative

x in list

O(n)

x in set or x in dict

s += x in a loop

O(n)

"".join(parts)

lst.pop(0)

O(n)

deque.popleft()

lst.insert(0, x)

O(n)

deque.appendleft()

lst.remove(x)

O(n)

Set, or mark as deleted

max(lst) repeatedly

O(n)

Running maximum, or a heap

s[1:] repeatedly

O(n)

Index arithmetic

del lst[0]

O(n)

deque

lst.index(x)

O(n)

Dict from value to index

sorted() inside a loop

O(n log n)

Sort once outside

# The running example the prose assumes. items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] words = ["quadratic", " ", "is", " ", "slow"] queue = list(range(6)) data = [3, 1, 4, 1, 5] s = "abcdef" running, seen = [], {} def process(ch): pass def main(): sum(range(1000)) # O(n^2) for key in data: if key not in list(seen.keys()): # list() then a linear scan ... # O(n) for key in data: if key not in seen: # dict membership is O(1) ... print("checked", len(data), "keys against a dict")

# The running example the prose assumes. items = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] words = ["quadratic", " ", "is", " ", "slow"] queue = list(range(6)) data = [3, 1, 4, 1, 5] s = "abcdef" running, seen = [], {} def process(ch): pass def main(): sum(range(1000)) # O(n^2): the inner comprehension runs per outer element dupes = [x for x in items if items.count(x) > 1] # O(n): count once from collections import Counter counts = Counter(items) dupes = [x for x in items if counts[x] > 1] print("dupes:", dupes)

import cProfile, pstats, io as _io def main(): total = 0 for i in range(20000): total += i return total # Profile.run() takes a callable, so it does not depend on the name being # importable from __main__ the way cProfile.run("main()") does. prof = cProfile.Profile() prof.enable() main() prof.disable() buf = _io.StringIO() pstats.Stats(prof, stream=buf).sort_stats("cumtime").print_stats(3) print("\n".join(buf.getvalue().splitlines()[:8]))

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

What is the complexity of this code?

Overview

The pattern

Step through it

What to watch

Say this out loud