Big-O for .NET Developers: Time and Space in LINQ

Learning outcome

By the end of this lesson you can state the cost of a LINQ line in three parts: time (how much work grows with input), extra space (memory beyond the source you already hold) and when the work happens. You will also separate average, amortized and worst-case costs, the three ideas interviewers most often blur.

All examples in this course are .NET 9 console programs (C# 13). Every output block was produced by compiling and running the code shown. Timings, where they appear, are one run on one machine and are labelled that way.

Intuition

Big-O describes how cost grows, not how long one call takes. O(n) means "doubling the input roughly doubles the work". O(1) means "the work does not depend on n". Two O(n) methods can differ by 10× in wall time; Big-O deliberately hides that constant.

For LINQ you need two numbers, not one:

n is the source size, m the size of a second sequence, k the number of distinct keys or results.

Deep dive

Average vs amortized vs worst case

• Average case is about likely inputs. HashSet<T>.Contains is O(1) on average because a good hash spreads keys across buckets. With a terrible hash (every key collides) it degrades to O(n) per lookup. Lesson 6 measures this.
• Amortized is about a sequence of operations. List<T>.Add is usually a write into spare capacity, but when the array is full it allocates a bigger array (double the size) and copies everything. Over n adds the total copying is less than 2n, so each add is O(1) amortized, even though one specific add is O(n).
• Worst case is the guarantee. List<T>.Contains is O(n) in the worst case (the item is last or missing).

Extra space is part of the answer

ToHashSet() gives O(1) lookups but costs O(n) extra memory, and the constant is larger than an array's: a set stores buckets, entries with cached hash codes and next pointers. In interviews, "I would trade O(n) memory for O(1) lookups" is a better answer than "use a HashSet".

Which collection operations matter for LINQ

Code example: count the work

// L01: count the work, not the milliseconds. n = 10,000.
const int n = 10_000;
var list = Enumerable.Range(0, n).ToList();
var set = new HashSet<int>(list);

// 1) List<T>.Add: amortized O(1), but the backing array is copied when it fills up.
var grow = new List<int>();
int resizes = 0, copiedElements = 0, lastCapacity = grow.Capacity;
for (int i = 0; i < n; i++)
{
    if (grow.Count == grow.Capacity && grow.Count > 0) copiedElements += grow.Count;
    grow.Add(i);
    if (grow.Capacity != lastCapacity) { resizes++; lastCapacity = grow.Capacity; }
}
Console.WriteLine($"List.Add x{n}: {resizes} resizes, {copiedElements} elements copied in total (< 2n = {2 * n}), final capacity {grow.Capacity}");

// 2) Membership: List.Contains scans (O(n)); HashSet.Contains hashes (O(1) average).
int listProbes = 0;
var probe = new CountingComparer();
bool foundInList = list.Contains(n - 1, probe); listProbes = probe.Calls;
probe.Calls = 0;
var countingSet = new HashSet<int>(list, probe); probe.Calls = 0;
bool foundInSet = countingSet.Contains(n - 1);
Console.WriteLine($"Contains(last): List made {listProbes} Equals calls; HashSet made {probe.Calls} Equals call(s) after 1 hash. Found: {foundInList}/{foundInSet}");

// 3) Space: the set is a second copy of the keys plus buckets.
long before = GC.GetAllocatedBytesForCurrentThread();
var copy = new HashSet<int>(list);
long setBytes = GC.GetAllocatedBytesForCurrentThread() - before;
before = GC.GetAllocatedBytesForCurrentThread();
var arr = list.ToArray();
long arrBytes = GC.GetAllocatedBytesForCurrentThread() - before;
Console.WriteLine($"Extra space for n={n}: int[] copy {arrBytes:N0} B; HashSet<int> {setBytes:N0} B (O(n) both, different constants)");
GC.KeepAlive(copy); GC.KeepAlive(arr); GC.KeepAlive(set);

sealed class CountingComparer : IEqualityComparer<int>
{
    public int Calls;
    public bool Equals(int x, int y) { Calls++; return x == y; }
    public int GetHashCode(int obj) => obj;
}

Output

List.Add x10000: 13 resizes, 16380 elements copied in total (< 2n = 20000), final capacity 16384
Contains(last): List made 10000 Equals calls; HashSet made 1 Equals call(s) after 1 hash. Found: True/True
Extra space for n=10000: int[] copy 40,024 B; HashSet<int> 161,808 B (O(n) both, different constants)

Code walkthrough

• 13 resizes for 10,000 adds: capacity went 4, 8, 16 … 16,384. The copies total 16,380 element moves, under the 2n bound that makes Add amortized O(1).
• List.Contains called Equals 10,000 times to find the last item. The HashSet computed one hash and made one Equals call.
• The HashSet<int> used about 4× the memory of an int[] copy for the same 10,000 values. Both are O(n) extra space; the constants differ.

Complexity summary

Failure modes

• Quoting only time. An answer without extra space is half an answer for any operator that buffers.
• Treating amortized as worst case. A latency-sensitive path can still feel the occasional O(n) resize; pre-size with new List<T>(capacity) when you know the count.
• Ignoring the hash-quality assumption. "HashSet is O(1)" assumes a good GetHashCode.
• Comparing constants with Big-O. "It is O(n) so it is fast" says nothing about a 5× constant factor.

Interview angle

A strong answer to "what is the complexity of this LINQ line?" names: the time, the extra space, the moment it runs (now or on enumeration), and the assumption it rests on (good hash, source is an IList<T>). Practise answering in that shape for every lesson in this course.

Practice questions

1. Why is List<T>.Add called O(1) when some calls copy the whole array?

Answer: The copies happen at doubling sizes, so n adds copy fewer than 2n elements in total. Spread over n calls, that is O(1) amortized per call. A single call can still be O(n).

2. What is the time and extra space of var set = list.ToHashSet(); bool b = set.Contains(x);?

Answer: Building is O(n) time and O(n) extra space; the lookup is O(1) average. If you do only one lookup, list.Contains(x) (O(n) time, O(1) space) is cheaper overall.

3. When can HashSet<T>.Contains be O(n)?

Answer: When many keys share a hash code (bad GetHashCode, or adversarial input), so one bucket holds most entries and the lookup compares against each.

Revision checklist

• Give time and extra space, plus when the work runs.
• Amortized O(1) is not "every call O(1)".
• Average O(1) hashing depends on hash quality.
• Same Big-O can hide large constant differences.

References

• Collections and data structures (Microsoft Learn)
• List<T>.Add remarks: O(1), or O(n) when capacity must grow
• HashSet<T> class
• List<T> source (dotnet/runtime)