What time and space cost do you state for a brute force with two nested loops and an inner scan?

## The method: price the innermost operation, then multiply outward The reliable way to state a brute force's cost is to ignore how many loops you see and instead ask two questions: how many times does the innermost work happen, and what does one unit of that work cost? For the fragment shown, the outer pair of loops walks every ordered pair of start positions `i < j`. That is n(n-1)/2 pairs, which is Θ(n^2). For each pair, the inner `while` compares characters at matching offsets until they differ or the scan runs off the end. That loop is *not* constant time: it can run up to n - j iterations. So the total is Θ(n^2) pairs multiplied by O(n) comparisons each, giving **O(n^3) worst-case time**. The most common wrong answer is "two nested loops, so O(n^2)". Counting loop headers is the trap; the `while` is a loop too, and its bound depends on n. ## Is the worst case reachable? Yes, and being able to name the input that triggers it is what separates a memorized answer from an understood one. Feed the fragment a sequence of one repeated symbol. Every pair of start positions matches for as long as the scan is allowed to run, so each of the ~n^2/2 pairs costs Θ(n) comparisons, and the total is Θ(n^3) — the upper bound is tight, not merely an over-estimate. On a sequence with few repeats, the `while` breaks after one or two comparisons for almost every pair, and the running time is close to quadratic. Both statements are true at once, and saying both is the strong answer: "O(n^3) worst case, driven by highly repetitive input; closer to O(n^2) on typical input." Note the direction of the claim carefully. O(n^3) is an **upper bound on the worst case**. It does not assert that the algorithm ever performs n^3 steps on your data, and it does not describe the average. Candidates who say "it is n^3, so it will take n^3 operations" have inverted the meaning of the notation. ## The space half of the answer, which is the half people drop Ask what memory the algorithm allocates *beyond the input it was given*. Here: two loop indices, a scan counter, and a best-so-far length. All of that is a constant number of values, so **auxiliary space is O(1)**. This is worth stating explicitly because the intuition "it is examining every segment, so it must be storing every segment" is wrong for this formulation. The fragment never materializes a segment; it compares positions in place and remembers only a length. That also shows how sensitive the space answer is to a small implementation choice. If the loop copied each candidate segment into a fresh buffer before comparing, auxiliary space would become O(n) for the live copy — and if it retained every candidate it examined, it would balloon to O(n^2) segments totalling O(n^3) characters. Same asymptotic time, entirely different memory profile. This is exactly why the two costs are stated separately rather than as one number. A further point candidates miss: **recursion depth is space**. This fragment is iterative, so there is nothing on the stack. Had the same enumeration been written recursively with depth proportional to n, the O(1) claim would become O(n) even though nothing was explicitly allocated. ## Saying it aloud, precisely A full statement has four parts: 1. **Define n.** "n is the number of positions in the input sequence." A complexity with an undefined variable is not a complexity. When the input has two dimensions — say m records of average length k — say so, because O(m^2 k) and O(n^3) can describe the same code with different variables and only one of them is honest. 2. **Time, with the case named.** "O(n^3) worst case." 3. **The trigger.** "Reached when the input is highly repetitive." 4. **Auxiliary space.** "O(1) extra; it compares in place." ## Why the precise statement matters for the baseline The baseline exists to define the gap you are about to close. If you state O(n^2) for something that is really O(n^3), every claim you make afterwards about the improvement is wrong by a factor of n — you might even "optimize" to something no faster than what you had. And if you state time but never space, an interviewer with a memory constraint in mind has no way to tell whether your approach is admissible at all. The stated cost is the contract the rest of the conversation runs on, so it is worth the extra ten seconds to make it exact.