.NET Collections Big-O Cheat Sheet

Learning outcome

By the end of this cheat sheet you should be able to state the time complexity of the common operations on every mainstream .NET collection, explain amortized O(1), and pick a collection from the access pattern rather than from habit. This is the one-page lookup table. For the reasoning behind each choice, see the C# Collections and Complexity Companion. For what LINQ adds on top of these collections, see Time and Space Complexity in LINQ.

Intuition

Every collection is one of a few shapes, and the shape decides the costs:

• Contiguous array (T[], List<T>, Queue<T>/Stack<T> as circular or array buffers): O(1) index access; inserting in the middle shifts elements, which is O(n).
• Hash table (Dictionary, HashSet, ConcurrentDictionary, frozen collections): O(1) average lookup, assuming a good GetHashCode.
• Balanced tree: sorted trees provide O(log n) key operations. ImmutableList uses an indexed tree but value search is O(n); ImmutableDictionary indexes hash buckets and does not sort by key.
• Linked nodes (LinkedList<T>): O(1) insert or remove when you already hold the node, but O(n) to find it.
• Heap (PriorityQueue): O(log n) enqueue and dequeue, O(1) peek at the minimum.

Quick reference: operation costs

n = count. "Amortized" means occasional O(n) resizes averaged over many operations. Hash-based O(1) entries are average/expected costs, not worst-case guarantees; collisions can make searches and removals O(n). Hashing, equality and comparison costs are assumed constant, and concurrent-operation timings also depend on contention.

Count (or array Length) is O(1) for the listed collections except ConcurrentDictionary, which takes locks. LINQ Count() can use collection counts or specialized iterator fast paths; otherwise it enumerates the sequence.

Sorting and searching

Choosing by access pattern

Failure modes

• list.Contains(x) inside a loop over another list: O(n·m). Build a HashSet<T> once for expected O(n + m) with suitable hashing.
• list.RemoveAt(0) in a loop to drain a list: O(n²). Use Queue<T>.
• List<T>.Insert(0, x) repeatedly: O(n²). Use LinkedList<T>, Queue<T>/Stack<T>, or build the list and reverse it.
• Mutable keys in a Dictionary/HashSet: changing equality/hash-relevant fields after insertion can make the key unfindable or violate uniqueness assumptions.
• Expecting PriorityQueue enumeration or Dictionary enumeration to be ordered.
• ImmutableList<T> used for index-heavy reads: O(log n) per index plus poor locality. ImmutableArray<T> is O(1).
• Poor hash codes (for example, everything returns 0) degrade Dictionary to O(n) per lookup.

Interview drill

1. Why is List<T>.Add "amortized O(1)" and not simply O(1)?
2. SortedDictionary vs SortedList: when does each win?
3. What is the worst case for Dictionary lookup, and what causes it?
4. How do you turn an O(n·m) "find matches" loop into O(n + m)?
5. Is PriorityQueue enumeration sorted? What is the complexity of Dequeue?
6. ImmutableArray<T> vs ImmutableList<T>: which is faster to index, and which is faster to "add" to?

Revision checklist

• Can I fill in the costs for List, Dictionary, HashSet, SortedDictionary, LinkedList, Queue and PriorityQueue from memory?
• Can I explain array doubling and why pre-sizing helps?
• Do I know which sorts are stable?
• Can I name the right collection for five access patterns?
• Do I know why ConcurrentDictionary.Count is expensive?

Worked executable example

The program shows List<T> capacity doubling, the effect of pre-sizing, the difference between linear and hashed Contains (by counting Equals calls), sorted vs heap ordering, and FIFO dequeue.

Run this example

Use the .NET 10 SDK. In a new empty folder, save the project below as Example.csproj and the listing as Program.cs. Run dotnet run --project Example.csproj.

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net10.0</TargetFramework>
    <ImplicitUsings>disable</ImplicitUsings>
    <Nullable>enable</Nullable>
  </PropertyGroup>
</Project>

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;

// 1) List<T> grows by doubling: Add is amortized O(1), an individual Add can be O(n).
var list = new List<int>();
var capacities = new List<int> { list.Capacity };
for (var i = 0; i < 20; i++)
{
    list.Add(i);
    if (list.Capacity != capacities[^1]) capacities.Add(list.Capacity);
}
Console.WriteLine($"List capacities: {string.Join(" -> ", capacities)}");

// 2) Pre-size when you know the count: no regrowth.
var sized = new List<int>(1_000);
for (var i = 0; i < 1_000; i++) sized.Add(i);
Console.WriteLine($"Pre-sized capacity after 1000 adds: {sized.Capacity}");

// 3) Contains: List scans O(n) with Equals; HashSet hashes O(1) on average.
var probe = new Probe();
var probes = Enumerable.Range(0, 1_000).Select(i => new Key(i, probe)).ToList();
var set = new HashSet<Key>(probes);
probe.EqualsCalls = 0;
probes.Contains(new Key(999, probe));
Console.WriteLine($"List.Contains(last) Equals calls: {probe.EqualsCalls}");
probe.EqualsCalls = 0;
set.Contains(new Key(999, probe));
Console.WriteLine($"HashSet.Contains Equals calls: {probe.EqualsCalls}");

// 4) Sorted collections keep order; PriorityQueue gives the minimum, not a sorted enumeration.
var sortedDict = new SortedDictionary<string, int> { ["c"] = 3, ["a"] = 1, ["b"] = 2 };
Console.WriteLine($"SortedDictionary keys: {string.Join(",", sortedDict.Keys)}");
var pq = new PriorityQueue<string, int>();
pq.Enqueue("low", 5); pq.Enqueue("urgent", 1); pq.Enqueue("mid", 3);
Console.WriteLine($"PriorityQueue dequeues: {pq.Dequeue()}, {pq.Dequeue()}, {pq.Dequeue()}");

// 5) Queue.Dequeue is O(1); draining a List with RemoveAt(0) is O(n) per call.
var q = new Queue<int>(new[] { 1, 2, 3 });
Console.WriteLine($"Queue.Dequeue: {q.Dequeue()}, remaining {q.Count}");

sealed class Probe { public int EqualsCalls; }

sealed class Key(int value, Probe probe) : IEquatable<Key>
{
    public int Value { get; } = value;
    public bool Equals(Key? other) { probe.EqualsCalls++; return other is not null && other.Value == Value; }
    public override bool Equals(object? obj) => Equals(obj as Key);
    public override int GetHashCode() => Value;
}

Expected output

List capacities: 0 -> 4 -> 8 -> 16 -> 32
Pre-sized capacity after 1000 adds: 1000
List.Contains(last) Equals calls: 1000
HashSet.Contains Equals calls: 1
SortedDictionary keys: a,b,c
PriorityQueue dequeues: urgent, mid, low
Queue.Dequeue: 1, remaining 2

The growth sequence (0 → 4 → doubling) is the current .NET implementation, not a documented contract. The documented guarantee is "O(1) unless the capacity must grow, then O(n)".

Related on TechInterviewNotes

• Time and Space Complexity in LINQ (course). Start with Big-O for .NET Developers, then see Contains, Any and Count: Fast Paths on List, HashSet and IEnumerable and Nested Queries O(n·m) vs Join and HashSet O(n+m)
• Choosing Collections and Understanding Their Complexity (Learn C# and .NET 10, lesson 13) and the C# Collections and Complexity Companion
• Frozen Collections in .NET: Comparers and Trade-offs
• ConcurrentDictionary: Thread Safety Is Not Workflow Atomicity
• Intermediate C# Equality and Hash Collections (course)

Sources

Microsoft Learn: Collections and data structures (algorithmic complexity table)

Microsoft Learn: List<T>.Add remarks

Microsoft Learn: Dictionary<TKey,TValue> remarks

Microsoft Learn: SortedDictionary<TKey,TValue> (vs SortedList)

Microsoft Learn: PriorityQueue<TElement,TPriority>

Microsoft Learn: Array.Sort (introsort, unstable)

Microsoft Learn: System.Collections.Frozen namespace

Microsoft Learn: ImmutableList<T> / ImmutableArray<T> guidance