vizlearn

What is the complexity of this code?

Interview QuestionsBy Updated

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 four shapes

1. x in a_list inside a loop. The membership test is O(n). Fix: build a set once, before the loop.

2. result += piece in a loop. Strings are immutable, so each step copies everything so far. Fix: collect into a list and "".join at the end.

3. list.pop(0) or insert(0, x). Both shift every other element. Fix: collections.deque.

4. sorted() inside a loop. Usually the data has not changed and the sort belongs outside it. Fix: sort once, or keep a heap if it really does change.

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)."

What is the complexity of this code?

Here is a loop. What is its complexity? (The four traps interviewers actually use.)

Why they survive code review

None of them looks wrong. Each line is idiomatic Python that would be fine on its own, and on a hundred elements every version is instant. The bug ships, and then someone doubles the input and everything takes four times as long.

The habit worth building is to read the cost of a line rather than its appearance, and to notice when a linear operation has ended up inside a loop. "What is this line's complexity, and how many times does it run?" catches all four.

How to answer in the room

Name the shape, give the complexity, and give the fix in one sentence: "the membership test is a linear scan, so it's O(n²) — build a set before the loop and it's O(n)". Do not hedge; these have definite answers.

If asked to prove it, double the input and show the time going up fourfold. That is what the program below does for all four.

Run it in Python

All four traps and all four fixes, each timed at two input sizes so you can watch the broken version quadruple while the fixed one doubles.

traps.pyPython 3
Output
How the code works
  1. lookup = set(pool)Built once, outside the loop. That single line converts O(n·m) into O(n + m) and is the fix for the most common trap of the four.
  2. parts.append(...) then "".join(parts)One allocation at the end instead of one per step. The Buf class exists so CPython's in-place string resize cannot hide the cost.
  3. q.popleft()deque is a doubly linked list of blocks, so both ends are O(1). A queue on a list is the second most common accidental quadratic.
  4. the growth columnThe number to read. Doubling the input roughly quadruples a quadratic and roughly doubles a linear one — which is how you demonstrate a complexity claim without arguing about it.
Change one thing
  • Double the sizes again. The ratios hold, which is the point of measuring growth rather than absolute time.
  • Move set(pool) inside the comprehension. It becomes worse than the list version — the fix is building it once, not using a set.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. for x in items: if x in a_list: ... has complexity:
  2. Which fixes a queue built on list.pop(0)?
  3. How do you demonstrate a quadratic without arguing about it?





 Cheat sheet
What is the complexity of this code?
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.
INTERVIEW · vizlearn.in/interview/accidental-quadratic-complexity.html
More in Interview
InterviewWhy are Python strings immutable?InterviewWhat does slicing a string cost?InterviewDoes len() count characters or bytes?InterviewWhat is the difference between str and bytes?
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.
About VizLearnGitHubLinkedInContact