Froze when asked for the time complexity of my own solution

Question

My code worked and the interviewer seemed happy. Then they asked "what's the complexity?" and my mind went blank. I said O(n) because there was one loop, and they asked me to look again. Inside the loop I had if x in seen, where seen was a list.

How do you work this out reliably under pressure, rather than guessing?

Hannah Lindqvist · Accepted Answer

Your loop is where the hidden cost was. x in seen on a list checks every element, so it is O(n) on its own. Inside an O(n) loop, that makes the whole thing O(n²). Change seen to a set and the lookup is O(1) on average, which brings you back to O(n). That is almost certainly the answer they were steering you to.

A routine that works under pressure:

Name n out loud: "n is the length of the input."
For each loop, say how many times it runs in terms of n.
For every line inside a loop, ask whether it is secretly a loop: in on a list, .index(), slicing, string concatenation in a loop, sorted() (n log n).
Multiply nested costs, add sequential ones, and keep the biggest term.
Then say the space too: "plus O(n) extra space for the set."

Saying the steps out loud matters as much as the answer. Interviewers are mostly checking that you have a method.

Fatima Zahra Benali · Answer

Step 3 is exactly what I missed. Adding "is this line secretly a loop?" to my notes. Thank you both.

Rafael Mendes · Answer

What helped me: after every practice problem, write the complexity in a comment before submitting, then check it. After about thirty problems it stops being something you work out and becomes something you just see.