Introduction

The Big O of a nested loop that calls Any() depends on what Any() is iterating over and whether it can short-circuit early. In the worst case, you multiply the cost of the outer loops by the worst-case cost of the Any() call.

Start With the Structure

Suppose you have code shaped like this in C#:

1foreach (var row in rows)
2{
3    foreach (var item in row.Items)
4    {
5        if (otherCollection.Any(x => x.Id == item.Id))
6        {
7            // do work
8        }
9    }
10}

Let:

• 'n be the number of rows'
• 'm be the number of items per row'
• 'k be the number of elements in otherCollection'

The outer loops run n * m times. Each Any() call may inspect up to k elements before it returns.

Worst-Case Complexity

Any() is not magic. On an ordinary sequence, Any(predicate) scans until it finds a match or reaches the end. So the worst case for one call is O(k).

That makes the overall worst-case complexity:

• 'O(n * m * k)'

The worst case happens when either:

• no element matches, so Any() checks the whole collection every time
• the matching element is always near the end

That is the correct Big O answer if the question asks for worst-case time complexity.

Why Any() Sometimes Feels Cheaper

Any() short-circuits. If the first element matches, it stops immediately. That can make the average runtime better in practice.

But Big O worst-case analysis does not reward that short-circuit unless you know something stronger about the data. Without such guarantees, you still analyze it as O(k) per call.

This is the same reason a linear search stays O(k) even though some searches end early.

Data Structure Choice Can Change the Answer

If otherCollection is turned into a HashSet<int> or another structure with fast membership lookup, the complexity changes a lot.

1var ids = new HashSet<int>(otherCollection.Select(x => x.Id));
2
3foreach (var row in rows)
4{
5    foreach (var item in row.Items)
6    {
7        if (ids.Contains(item.Id))
8        {
9            // do work
10        }
11    }
12}

Now membership testing is approximately O(1) on average, so the nested loop becomes:

• build set: O(k)
• scan nested loops: O(n * m)
• total: O(k + n * m)

That is usually much better than repeatedly calling Any() over the same sequence.

Always Ask What Any() Is Running On

Not all Any() calls cost the same. Examples:

• 'list.Any(predicate) is linear in the list length in the worst case'
• 'query.Any() against a database may translate to SQL and involve index behavior'
• 'enumerable.Any() on a generator may execute deferred work on each call'

So the right complexity answer depends on the underlying source, not just on the method name.

Common Pitfalls

One common mistake is saying Any() is always O(1) because it "just checks if something exists." That is only true for Any() without a predicate on some sources that can answer emptiness immediately. Any(predicate) is usually a search.

Another issue is ignoring repeated work. Calling Any() inside nested loops often means scanning the same collection again and again.

It is also easy to mix up average behavior and worst-case complexity. Short-circuiting can help actual runtime, but worst-case Big O still uses the full scan when no better guarantee exists.

Summary

• In the usual case, nested loops plus Any(predicate) give worst-case complexity O(n * m * k).
• 'Any() short-circuits, so average runtime may be better than the worst case.'
• The answer depends on what collection Any() is iterating over.
• Repeated Any() calls inside loops often signal an optimization opportunity.
• Converting the searched collection into a hash-based lookup can reduce the complexity dramatically.