Learn

Before you say the complexity, say what n is

3 November 2026 · Explain it out loud

The code works and the interviewer asks the question you knew was coming: "What's the complexity?" You say "n log n" quickly, because it sounds right. Then the follow-up arrives, "n of what?", and you realise you never decided.

The situation

A short task, said aloud: "Given a list of usernames, return the distinct ones in alphabetical order, ignoring case."

Two lines do it:

def unique_names(names):
    return sorted({n.lower() for n in names})

On ["Team-B", "team-a", "TEAM-B"] it returns ['team-a', 'team-b']. On an empty list it returns []. The Java version is just as short:

static List<String> uniqueNames(List<String> names) {
    return names.stream()
            .map(n -> n.toLowerCase(Locale.ROOT))
            .distinct()
            .sorted()
            .toList();
}

Locale.ROOT matters: without it, lowercasing follows the machine's locale, and on a Turkish locale "TEAM-I" does not become "team-i". That is worth one sentence aloud too.

Where "n log n" goes wrong

There are two sizes in this input, not one: how many names there are, call it n, and how long the longest name is, call it L. Every step touches characters, not just names.

• Lowercasing one name reads all of it: O(L) per name, O(n·L) in total.
• Putting a string in a set hashes it, which also reads all of it: O(n·L) again.
• Sorting makes about n log n comparisons, and comparing two strings can read up to L characters each time, when they share a long prefix.

So the honest worst case is O(n·L·log n) time and O(n·L) space. "n log n" is true only if L is treated as a constant.

Treating L as a constant is often the right call. Usernames of up to thirty characters are a constant for most purposes. But it is a call, and it belongs to you only if you say it. If the interviewer has in mind ten thousand file paths that all start with the same hundred-character directory, every comparison in the sort walks that prefix, and the L you dropped is the biggest number in the room.

The same trap appears on a grid. A search that visits every cell of a square board is O(n²) if n is the side and O(n) if n is the number of cells. Both are correct. Said without the definition, one of them sounds wrong to whoever assumed the other.

What to say out loud

Four sentences, in this order.

Name the sizes first: "Let n be the number of names and L the length of the longest one." Ten seconds, and every claim after it can be checked.

Count each line, not the whole function: "Lowercasing is n times L. The set is n times L on average, for the hashing. The sort is n log n comparisons, each up to L." You are reading your own code from the inside, out loud, and the interviewer can stop you at the line they disagree with instead of at the total.

Give the total, then the assumption that shortens it: "So n L log n in the worst case. If names are short, say under fifty characters, I'd treat L as constant and call it n log n. Is that a fair assumption here?" A yes costs nothing. A no tells you the round is about strings.

Add space without being asked: "Space is n times L for the set and the output." Interviewers ask about space often enough that offering it reads as a habit, not a guess.

If you need a moment before any of this, mark it: "Give me fifteen seconds to count it on the code." Then count on the code, line by line, not in your head.

The exercise

1. Take three solutions you wrote this month. For each, write down every size in the input: number of items, length of each item, number of queries, the alphabet.
2. Beside each line of code, write its cost in those sizes. Lines that call a library function (sorted, in, contains, toLowerCase, string slicing) get the cost of what the function reads, not "1".
3. Write the total, then the one assumption under which it shrinks, as a question you could ask the interviewer.
4. Say all four sentences aloud with a timer. Under forty seconds is the target; if you run over, the per-line part is too detailed for the lines that do not matter.
5. Pick one of the three and invent an input on which the dropped size dominates, such as long shared prefixes or a single enormous item. Say why the short answer would have been wrong on it.

Where this fits in Gadfly

Gadfly has four rooms, and in the algorithms room you code in Java or Python while the tutor speaks English. In tutor mode it asks the next question rather than revealing the solution, so "what is n here?" is the kind of question it puts to you after you name a complexity. Mock mode behaves like an interviewer instead: no coaching during the round, and a debrief at the end quoted from the record of what you said.