Introduction

The answer depends on what “processing all consecutive subsequences” actually means. There are O(n^2) consecutive subsequences in a list of length n, so just enumerating their start and end positions is already quadratic. But if you also copy or rescan each subsequence naively, the total cost can become cubic.

That is why people argue about O(n^2) versus O(n^3). They are often analyzing different operations under the same informal description.

How Many Consecutive Subsequences Exist?

For a list of length n, every consecutive subsequence is defined by a start index and an end index with start <= end.

The number of such pairs is:

• 'n choices starting at index 0'
• 'n - 1 choices starting at index 1'
• and so on

So the total count is:

• 'n + (n - 1) + ... + 1'
• which is n(n + 1) / 2

That is O(n^2) subsequences.

Enumerating Boundaries Is O(n^2)

If your code only loops over all start and end pairs, it is quadratic.

1n = len(arr)
2for start in range(n):
3    for end in range(start, n):
4        # do O(1) work about the window [start:end+1]
5        pass

This is O(n^2) because the inner loop runs a triangular number of times and the body is assumed to be constant time.

Copying Each Subsequence Makes It O(n^3)

If the body creates a fresh slice each time, the work is no longer constant. Copying a subsequence of length k costs O(k).

for start in range(n):
    for end in range(start, n):
        window = arr[start:end+1]

Now the total cost is the sum of all subsequence lengths. That grows to O(n^3).

The same is true if you recompute the sum of each window from scratch instead of maintaining incremental state.

A Concrete Example

Suppose you want the sum of every consecutive subsequence.

Naive version:

for start in range(n):
    for end in range(start, n):
        total = sum(arr[start:end+1])

The sum(...) call scans the current window every time, so the total complexity is O(n^3).

Improved version:

1for start in range(n):
2    total = 0
3    for end in range(start, n):
4        total += arr[end]
5        # total is sum of arr[start:end+1]

Now each extension of the window is O(1), so the total becomes O(n^2).

The Key Distinction

There are really two separate questions:

• how many consecutive subsequences are there?
• how much work do you do per subsequence?

The first answer is always quadratic. The second determines whether the whole algorithm stays quadratic or rises to cubic or worse.

That is why big-O discussions about subsequences often sound contradictory when they are actually discussing different definitions of “process.”

When O(n^2) Is Unavoidable

If the problem truly requires producing some output for every consecutive subsequence, you cannot do better than O(n^2) overall because there are already that many outputs.

What you can avoid is the extra factor caused by rescanning or copying every window from scratch.

That is the real optimization opportunity in most of these problems.

Common Pitfalls

A common mistake is calling the whole algorithm O(n^2) just because there are two visible loops, without checking whether the inner work is itself linear in subsequence length.

Another mistake is calling it O(n^3) automatically whenever slices are involved, even if the algorithm only tracks boundaries and does not copy data.

Developers also mix up “number of subsequences” with “cost of processing all subsequences.” Those are related but not identical questions.

Finally, if the goal is some aggregate such as sums or maxima, prefix sums or incremental updates often remove the extra factor cleanly.

Summary

• There are O(n^2) consecutive subsequences in a list of length n.
• Enumerating start and end boundaries with O(1) work per subsequence is O(n^2).
• Copying or rescanning each subsequence naively usually makes the total O(n^3).
• The real question is the cost per subsequence, not just the number of loops.
• Many “naive” cubic subsequence algorithms can be reduced to quadratic by maintaining incremental state.