Dotnet LINQ expressions time complexity

Question

Considering elements as a list of objects (already loaded in memory, not a DB query) and given the following portion of code:

var filteresElements = elements.Where(el => el.Flag == true).Select(el.Id).ToList();

What is the time complexity of this row? Is elements looped twice or just once?

Clarification: the question is not related to a real life problem, when I wrote the question I thought at elements as a generic List but you can elaborate your question on whatever Iterable object you like: the point of the question is how LINQ expression iterate over in memory data structures.

When it comes to complexity, constants do not matter. Therefore it doesn't matter if the elements are traversed once or twice (e.g. it's O(n) anyway in a linear container). See Big O notation. — wohlstad
– wohlstad, Commented Sep 8 at 8:06
In order to complete the question: What is elements ? Please post a minimal reproducible example. — wohlstad
– wohlstad, Commented Sep 8 at 8:16
Impossible to answer without knowing what elements actually is. Iterating a dictionary is a lot more expensive than iterating an array or list. The container's iterator implementation also matters - what if the container is a weird tree on Flag that returns two separate lists? Or it's a Lookup or other grouping on Flag in which case all True elements are in the same internal array? — Panagiotis Kanavos
– Panagiotis Kanavos, Commented Sep 8 at 8:18
A lot of containers with a non-linear interface (eg Queue) actually use TElement[] buffers internally for performance reasons - data locality matters and the N of indirect RAM access can be orders of magnitude bigger than the N of working with a buffer in the CPU cache. — Panagiotis Kanavos
– Panagiotis Kanavos, Commented Sep 8 at 8:21
@wohlstad It's just out of personal curiosity: if we are being meticulous it would be O(n) vs O(2n) which is still linear but one is twice the other; — hello-there
– hello-there, Commented Sep 8 at 14:22

PRISHUSOFT.COM · Accepted Answer · 2025-09-08 08:02:24Z

1

var filteredElements = elements
    .Where(el => el.Flag == true)
    .Select(el => el.Id)
    .ToList();

Time complexity: O(n) – each element is inspected once.

Looping:

The elements are not looped twice. LINQ uses deferred execution, so Where and Select are combined into a single iteration when ToList() forces evaluation.

So, the list is traversed only once to apply both the filter and the projection.

answered Sep 8 at 8:02

PRISHUSOFT.COM

621 bronze badge

Sign up to request clarification or add additional context in comments.

4 Comments

wohlstad Sep 8 at 8:08

It could be O(n) regardless of how many times an elements is accessed - as long as it is constant.

Panagiotis Kanavos Sep 8 at 8:12

This makes the incorrect assumption that iterating elements doesn't cost. What if this is a dictionary or any other container where access is not constant?

Richard Sep 8 at 10:43

In .NET Dictionary<T> has item lookup (or other single element operation) time complexity of asymptotically O(1) (as .NET uses hash based dictionaries). Iteration is O(n) as the underlying storage is a single array like object.

Panagiotis Kanavos Sep 8 at 11:11

Indeed, but that proves my point - it depends on the internal implementation. A SortedDictionary and SortedSet don't use an internal array. But a HashSet does. A ConcurrentDictionary doesn't.

Collectives™ on Stack Overflow

Dotnet LINQ expressions time complexity

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related