How Do You Analyze Nested Loops?

It is still quadratic, because the inner loop never runs a full n times for every outer iteration. It runs the remaining distance instead, so the total is a triangular number rather than a square, and a triangular number is still proportional to n squared.

def count_pairs(n):
    steps = 0
    for i in range(n):
        for j in range(i, n):
            steps += 1
    return steps

for n in (4, 8, 16):
    print(n, count_pairs(n))

The counts are 10, 36 and 136, which is n times n plus one, divided by two. Now look at what happens when n doubles: 10 becomes 36, and 36 becomes 136. The work grows by roughly four times each time n doubles, and four times the input is the signature of a quadratic bound. The halving of the constant does not change the growth rate, it only changes the factor in front.

The general rule for reading nested loops: if the inner bound is independent of the outer variable, the costs multiply. If the inner bound is derived from the outer variable, you have to add up the actual number of iterations, which often collapses to a single term once you simplify the arithmetic series. If the inner loop is conditional on data rather than on the index, you have an input-sensitive bound and should state the worst case.

The trade-off to mention is that constant factors hidden inside a quadratic are worth attacking only after the exponent is right. Turning the triangular loop into a genuine single pass changes the complexity class; removing a factor of two from the constant does not. In an interview, say which one you are doing.

It is linear in the total number of elements, not quadratic in the number of rows and columns. The two loops are nested in the source, but the inner loop does not repeat the full work for each row: it repeats only over the elements that row actually contains.

rows = [[1, 2, 3], [4, 5], [6]]
total = 0
for row in rows:
    for value in row:
        total += value
print(total, sum(len(row) for row in rows))

The output is 21 and 6. The second number is the count of elements actually visited, and it is the number that determines the cost. Reading it as linear in the total element count is exactly right: six elements means six visits, and if you doubled the elements you would double the work.

The trap this question sets is the one where someone assumes a nested loop is automatically quadratic. That is only true when both loops run the full range every time. If the inner list always had the same length as the outer list had rows, then a naive reading would give n squared, and in that special case it genuinely is. When the row lengths vary, the bound should be expressed as the sum of the row lengths, and in the worst case where every row has n entries, that sum is again n squared.

The trade-off to name is that the bound is only as good as the structure. If rows can be ragged, compute the total element count once rather than assuming a shape, because the loop itself does not care but the analysis does. And if you find yourself needing random access by coordinate, a flattened list plus an index map is usually faster than a list of lists.

Break the loop body into its own cost function and combine the two. If the body costs b(n) per iteration and the loop runs k times, the total is b(n) times k. That handles the classic mistake of treating every iteration as one unit when the body is really doing a linear scan, a sort, or an allocation of size n.

When the iteration count depends on the data, there is no single answer, and the honest approach is to give a bound parameterised by that data. If a loop runs once per element of a list of unknown length, the bound is O(n) in the length of that list, and you should say which list. If the loop runs until a condition becomes false, state the worst case in terms of the maximum number of iterations the condition can permit, and separately note the best case where it exits immediately.

Be careful with one specific trap: a loop that calls a function whose cost depends on the current state. A loop over n elements that calls a linear search on each element is cubic, not quadratic, and if the search itself does a nested scan it can get worse. When you spot a call inside a loop, look up its cost rather than assuming it is constant.

The practical interview habit is to narrate the analysis as you go: state what n is, name the cost of the body, count the iterations, and multiply. If the interviewer challenges any step, you have made it easy for them to argue with one piece at a time instead of a conclusion you cannot defend. It also demonstrates that you reason about complexity from first principles rather than pattern-matching a template.