C# Collections Time Complexity for Interviews

Updated · By

In C#, List<T> indexing is O(1), Add is O(1) unless the list must grow, and Insert, RemoveAt near the front and Contains are O(n). Dictionary lookups approach O(1), HashSet Add and Contains are O(1), and SortedDictionary operations are O(log n). List.Sort is O(n log n) but unstable. The docs give no figure for PriorityQueue.

Where these figures come from

Every figure below is from the .NET API reference on Microsoft Learn, where each method's Remarks section states its cost. They were read on November 12, 2026, in the .NET 11 version of the pages, and the .NET 9 version gives the same figures.

The wording is worth keeping. List methods are "an O(1) operation" or "an O(n) operation, where n is Count". Dictionary methods only "approach" O(1), which is the documentation's way of saying average case, since the class page adds that "the speed of retrieval depends on the quality of the hashing algorithm" of the key type.

List<T>

From the List<T> method pages. List<T> is an array that grows, so the cost of a change depends on how many elements sit after it.

OperationCostNote
list[i], get or setO(1)
list.Add(x)O(1), or O(n) when it grows"If Count is less than Capacity, this method is an O(1) operation."
list.Insert(i, x)O(n)n is Count.
list.RemoveAt(i)O(n), where n is Count - iSo RemoveAt(0) is the most expensive call, and removing the last item is cheap.
list.Remove(x)O(n)"This method performs a linear search."
list.Contains(x), list.IndexOf(x)O(n)Linear search.
list.BinarySearch(x)O(log n)The list must already be sorted.
list.Sort()O(n log n)Unstable: equal elements may change order.

Dictionary<TKey,TValue>

The class page says "retrieving a value by using its key is very fast, close to O(1), because the Dictionary<TKey,TValue> class is implemented as a hash table." The method pages say "approaches an O(1) operation."

OperationCostNote
dict[key], get or setApproaches O(1)
dict.TryGetValue(key, out v)Approaches O(1)One lookup, where ContainsKey then the indexer is two.
dict.ContainsKey(key)Approaches O(1)
dict.Add(key, value)Approaches O(1), or O(n) when it growsO(n) "if the capacity must be increased."
dict.Remove(key)Approaches O(1)
dict.ContainsValue(v)O(n)A linear search, the docs say.

HashSet<T>

From the HashSet<T> method pages, which state flat O(1) rather than "approaches."

OperationCostNote
set.Contains(x)O(1)
set.Add(x)O(1), or O(n) when it resizes"If the HashSet<T> object must be resized, this method becomes an O(n) operation."
set.Remove(x)O(1)

SortedDictionary<TKey,TValue>

SortedDictionary "is a binary search tree with O(log n) retrieval." Use it when you need keys in order. Its page compares it with SortedList, which has the same O(log n) retrieval but slower changes: SortedDictionary "has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList."

OperationCostNote
sd.Add(key, value)O(log n)
sd.ContainsKey(key)O(log n)
sd.Remove(key)O(log n)
sd.ContainsValue(v)O(n)

Queue<T>, Stack<T> and PriorityQueue

Queue<T> and Stack<T> follow the same pattern as List.Add: adding is O(1) unless the internal array has to grow, when it is O(n).

OperationCostNote
queue.Enqueue(x)O(1), or O(n) when it grows
queue.Dequeue()O(1)This is why a Queue beats list.RemoveAt(0).
stack.Push(x)O(1), or O(n) when it grows
stack.Pop()O(1)

PriorityQueue<TElement,TPriority> is the exception. Its page describes it as "an array-backed, quaternary min-heap" and gives no Big O for Enqueue, Dequeue or Peek. A heap is what you can reason from, but say that you are reasoning, not quoting. The page also warns that "the type does not guarantee first-in-first-out semantics for elements of equal priority."

LINQ gotchas

LINQ hides loops, and its documentation says when. These are the lines to know, each from the method's own page:

MethodWhat the docs sayWhat it means
Count()"If the type of source implements ICollection<T>, that implementation is used." Otherwise "this method determines the count."O(1) on a List, a full pass on a query.
ElementAt(i)Uses the IList<T> indexer if there is one. Otherwise it "obtains the specified element."Indexing a query walks it.
Contains(x)Calls the collection's own Contains if it implements ICollection<T>.Fast on a HashSet, a scan on a List or a query.
Any()"The enumeration of source is stopped as soon as the result can be determined."Use Any() to test for emptiness, not Count() > 0.
OrderByDeferred execution, and "this method performs a stable sort."Stable, unlike List.Sort, and it runs only when enumerated.
ToList()"Forces immediate query evaluation."Do this once if you will enumerate a query more than once.

Deferred execution is the gotcha that costs the most. A query "is not executed until the object is enumerated," so a filtered query you call Count() on and then loop over runs twice.

Sorting and strings

List<T>.Sort and Array.Sort state O(n log n) and describe the algorithm: an introspective sort that uses insertion sort for partitions of 16 elements or fewer, heapsort "if the number of partitions exceeds 2 log n," and quicksort otherwise. Both say "this implementation performs an unstable sort." When equal elements must keep their order, use OrderBy, which is stable.

Strings are immutable. The StringBuilder page says "each operation that appears to modify a String object actually creates a new string," and recommends StringBuilder when a loop makes an unknown number of changes. It adds a warning of its own: indexing a large StringBuilder with Chars[] is typically O(n), and iterating its characters that way is O(n^2).

Common interview traps

Each pair is a slow version that passes small tests and the version the figures above point to.

C#

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

static class Choices
{
    // 1. A List as a queue: RemoveAt(0) is O(Count) per call.
    static List<int> DrainSlow(List<int> tasks)
    {
        var order = new List<int>();
        while (tasks.Count > 0) { order.Add(tasks[0]); tasks.RemoveAt(0); }
        return order;
    }

    static List<int> Drain(IEnumerable<int> tasks)
    {
        var queue = new Queue<int>(tasks);
        var order = new List<int>(queue.Count);
        while (queue.Count > 0) order.Add(queue.Dequeue());   // O(1) each
        return order;
    }

    // 2. List.Contains inside a loop is O(n) per check; HashSet is O(1).
    static List<int> FirstSeen(IEnumerable<int> items)
    {
        var seen = new HashSet<int>();
        return items.Where(x => seen.Add(x)).ToList();
    }

    // 3. One lookup instead of two.
    static void Increment(Dictionary<string, int> counts, string word)
    {
        counts.TryGetValue(word, out var n);   // n is 0 when missing
        counts[word] = n + 1;
    }

    // 4. String += in a loop builds a new string every time.
    static string Join(IEnumerable<string> words)
    {
        var sb = new StringBuilder();
        foreach (var w in words) sb.Append(w);
        return sb.ToString();
    }

    // 5. A deferred query runs again on every enumeration.
    static void Report(IEnumerable<int> scores)
    {
        var passed = scores.Where(s => s >= 50).ToList();   // run once
        if (passed.Any()) System.Console.WriteLine(passed.Count);
    }
}

One more needs no code: sorting with List.Sort and expecting ties to stay in their original order. The docs call it unstable, so sort by both keys or use OrderBy.

How to say it out loud

What a strong candidate might say

I'll track visited nodes in a HashSet, where the docs give Add and Contains as O(1), and use a Queue rather than removing from the front of a List, since RemoveAt is O(n) in the number of elements after the index. So the search is O(V + E) time and O(V) space. If I needed keys in order I'd switch to a SortedDictionary and pay O(log n) per operation.

What a strong candidate might say

I'm calling ToList on the filtered query once, because it's deferred: without that, counting it and then looping over it would run the filter twice.

Being exact about "approaches an O(1) operation" for Dictionary and about deferred execution in LINQ is what separates a C# answer from a generic one. Practice it in a coding mock interview, and see the Big O cheat sheet for the structures in general.

What the docs do not state

These have no figure on the pages read for this guide, so none has a cost above:

  • PriorityQueue: no Big O for Enqueue, Dequeue, Peek or anything else, only that it is a quaternary min-heap.
  • Dictionary: no worst case, only "approaches an O(1) operation" and the dependence on the key's hash.
  • Enumerable.Count, ElementAt and Contains: no Big O, only when they use the collection's own implementation.
  • Enumerable.Last: no cost, and nothing on whether it uses an IList<T> indexer.
  • String concatenation with +: no figure, only that each operation creates a new string.

Complexity by language

Each language page takes its figures from that language's own documentation, cites it, and says what the documentation leaves out. TypeScript runs as JavaScript, so its costs are on the JavaScript page.

For the structures and algorithms themselves, see the Big O cheat sheet and sorting algorithm complexity.

Frequently asked questions

Is Dictionary lookup O(1) in C#?

The .NET documentation says retrieving a value by its key is close to O(1) because Dictionary is a hash table, and its methods approach an O(1) operation. It adds that the speed depends on the quality of the key type's hashing algorithm, so say on average when you state it.

What is the time complexity of List.Add in C#?

O(1) when Count is less than Capacity. When the list has to grow, that call becomes O(n), where n is Count, so Add is cheap on average across many calls. Insert is O(n), and RemoveAt is O(n) where n is Count minus the index.

What is the time complexity of PriorityQueue in C#?

The documentation does not state one. It describes PriorityQueue as an array-backed, quaternary min-heap, which is what you can reason from, but it gives no Big O for Enqueue, Dequeue or Peek. It also does not guarantee first-in-first-out order for elements of equal priority.

Is List.Sort stable in C#?

No. List.Sort and Array.Sort use an introspective sort and are O(n log n), and the documentation says they perform an unstable sort, so equal elements may change order. Enumerable.OrderBy performs a stable sort when you need ties kept in order.

Know the complexities? Now explain them out loud.

3 interviews a month on the Free plan, up to 20 minutes each. No card needed.