A strong answer
I start by naming the input size, usually n, and deciding what counts as one step: an operation whose cost doesn't depend on n, such as an arithmetic operation, a comparison or reading one array element.
Then I find the line that runs most often and count how many times it runs as a function of n. A loop over the input runs n times; a loop inside it multiplies, so two nested loops over the input give n², and an inner loop that starts after the outer index gives n(n − 1)/2, which is still O(n²). A loop that halves its range each pass runs about log₂ n times. Loops that come one after the other add, so the larger one wins.
Next I check every library call inside a loop, because many hide a loop of their own: membership tests on lists, index, slicing, copying, inserting at the front of an array, string concatenation with immutable strings. A loop over n items calling one of those is O(n²), not O(n).
For recursion, I count the calls and the work per call, often by drawing the tree of calls, which the recursion module covers.
Finally I simplify: keep the fastest-growing term and drop constants. And I say which case I mean, worst case unless stated otherwise, and give the extra space as well.
What the interviewer is listening for
- A method, not a guess: input size, step, the line that runs most, multiply nested loops.
- Awareness of hidden loops in library calls.
- Correct simplification, and a statement of the case and the space.
Common mistakes
- Counting loops by how deeply they are indented instead of how many times they run. A nested loop whose inner part runs a fixed 26 times is O(n).
- Missing the cost of a library call inside the loop.
- Forgetting a second input: an n × m grid is O(n·m), not O(n²).