Skip to content
Tutorials Center
My learning

Topics

C# Reference ยท Collections

Collection complexity (Big-O)

A Big-O cheat sheet for .NET collections: List, Dictionary, HashSet, SortedSet, Queue, Stack, LinkedList and PriorityQueue, with a counting demo you can run.

Every .NET collection makes trade-offs between lookup, insertion, removal and memory. Big-O notation describes how the cost grows as the number of items n grows: O(1) stays flat, O(log n) grows slowly, O(n) grows in step with the size and O(nยฒ) explodes. Picking the right collection is usually worth more than tuning a loop.

The numbers below are the documented or well-known complexities for the standard implementations. Constant factors differ a lot: a List<T> scan of 20 items often beats a Dictionary lookup because the data sits in one block of memory.

The table

Collection Index / get by key Search by value Add Insert / remove in the middle Notes
T[] O(1) O(n) fixed size n/a Fastest iteration, no growth
List<T> O(1) O(n) O(1) amortized O(n) Add at the end is cheap; Insert(0, x) shifts everything
LinkedList<T> O(n) O(n) O(1) at either end or at a node you hold O(1) at a node you hold Poor cache behavior, extra node allocation
Dictionary<K,V> O(1) average O(n) O(1) amortized O(1) average Worst case O(n) with bad hash codes
HashSet<T> O(1) average (Contains) O(1) average O(1) amortized O(1) average No order
SortedDictionary<K,V> O(log n) O(n) O(log n) O(log n) Red-black tree, ordered keys
SortedSet<T> O(log n) O(log n) O(log n) O(log n) Ordered; Min/Max are O(log n)
SortedList<K,V> O(log n) O(n) O(n) O(n) Two arrays, cheapest memory of the sorted types
Queue<T> Peek O(1) O(n) Enqueue O(1) amortized Dequeue O(1) Circular buffer
Stack<T> Peek O(1) O(n) Push O(1) amortized Pop O(1) Array-based
PriorityQueue<E,P> Peek O(1) O(n) Enqueue O(log n) Dequeue O(log n) 4-ary heap; no fast removal of arbitrary items
ImmutableList<T> O(log n) O(n) O(log n) O(log n) Balanced tree
ImmutableArray<T> O(1) O(n) O(n) (copies) O(n) Thin wrapper over an array

"Amortized" means that an occasional resize costs O(n), but spread over many adds the average is constant.

Try it

C# Counting comparisons

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

C# Cost of inserting at the front

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

Usage notes

  • Use a HashSet<T> or Dictionary<K,V> when you call Contains or look up by key repeatedly; List<T>.Contains in a loop is the classic accidental O(nยฒ).
  • Dictionary and hash set speed assume a good GetHashCode. A constant hash code makes every lookup a linear scan.
  • List<T>.Remove(x) is O(n) twice (find, then shift). Removing from the end with RemoveAt(Count - 1) is O(1).
  • LINQ operations add their own cost: Count() on an IEnumerable<T> that is not a collection walks the whole sequence, and ElementAt on a LinkedList<T> is O(n).
  • Enumerable.OrderBy is O(n log n); Distinct, GroupBy and ToHashSet are O(n) on average using hashing.
  • Constant factors and memory locality matter: arrays and lists of structs are the fastest to scan, and tree-based collections allocate a node per item.
  • Measure with a benchmark before replacing a simple List<T> for performance reasons; small n rarely cares.