SpaceComplexity

C# Built-In Time Complexity: The Interview Cheat Sheet

May 29, 202610 min read
dsaalgorithmsinterview-prepdata-structures
C# Built-In Time Complexity: The Interview Cheat Sheet
TL;DR
  • List<T> appends in O(1) amortized; insert or remove anywhere else is O(n) due to shifting
  • Dictionary<K,V> and HashSet<T> are O(1) average; use TryGetValue, never the bare indexer on an unknown key
  • SortedDictionary is O(log n) everywhere (red-black tree); SortedList is O(n) insert but adds O(1) positional access via Keys[i]
  • PriorityQueue<E,P> (.NET 6+) is a min-heap; no decrease-key, so use lazy deletion for Dijkstra
  • Array.Sort and List<T>.Sort are unstable introsort; LINQ OrderBy is stable and allocates a new array
  • Comparator subtraction overflow: never use (a, b) => a - b; use a.CompareTo(b) instead
  • String concatenation in a loop is O(n²); use StringBuilder.Append for O(n)

You know the algorithm. Then you reach for SortedList instead of SortedDictionary and your O(log n) solution quietly becomes O(n). Or you use the Dictionary indexer on a key that might be missing and your code throws in front of the interviewer. The interview doesn't end immediately. It just starts feeling like it should. This is the C# collection time complexity reference for every structure you will actually use.

C# Built-In Time Complexity: The Full Table

StructureAddLookupRemoveOrdered?
List<T>O(1) amortized / O(n) middleO(n) scanO(n)No
Dictionary<K,V>O(1) avgO(1) avgO(1) avgNo
HashSet<T>O(1) avgO(1) avgO(1) avgNo
SortedDictionary<K,V>O(log n)O(log n)O(log n)Yes
SortedList<K,V>O(n)O(log n)O(n)Yes, + index
SortedSet<T>O(log n)O(log n)O(log n)Yes
Queue<T>O(1) amortizedO(n)O(1)FIFO only
Stack<T>O(1) amortizedO(n)O(1)LIFO only
LinkedList<T>O(1) with nodeO(n)O(1) with nodeNo
PriorityQueue<E,P>O(log n)O(1) peekO(log n)By priority

"Amortized" means the array resizes occasionally, but across many operations the per-operation cost averages out. If you say O(1) without the qualifier, an interviewer will push back. Not might. Will. Say O(1) amortized.

List<T> Appends Fast. Everything Else Costs a Shift.

List<T> is a resizing array. Random access by index is O(1). Appending to the tail is O(1) amortized: .NET doubles capacity on overflow (4, 8, 16, ...), so the cost of copying is spread across all the appends that preceded it. Insert or remove at any other position shifts everything after it: O(n).

var list = new List<int>();
list.Add(42);                   // O(1) amortized
list.Insert(0, 42);             // O(n), shifts all elements right
list.RemoveAt(0);               // O(n), shifts all elements left
list.RemoveAt(list.Count - 1);  // O(1), last element, no shift
list.Remove(42);                // O(n), linear scan, then shift
list.Contains(42);              // O(n), no hash involved
list[i];                        // O(1), random access

RemoveAt(list.Count - 1) is the one free remove. Everything else costs a scan, a shift, or both. Nobody told you this in the beginning. Now you know.

Raw T[] arrays have the same O(1) access but don't resize. If you know the size upfront, an array is lighter. Array.Sort and Array.BinarySearch work on both.

O(1) Average. Unless You Throw.

Dictionary<TKey, TValue> is O(1) average for get, set, contains, and remove. The internals keep a _buckets array of slot indices and a flat _entries array of (hashCode, next, key, value) tuples. Collisions chain through the next index inside the entry array itself, keeping the data cache-friendly without allocating linked list nodes. See how hash maps actually work for the proof that expected chain length stays bounded.

var map = new Dictionary<string, int>();
map["a"] = 1;
map.TryGetValue("a", out int v);   // O(1), one hash lookup
map.ContainsKey("a");              // O(1)
map.GetValueOrDefault("b", 0);     // O(1), no throw
map.Remove("a");                   // O(1)

Never do ContainsKey followed by the indexer. That is two hash lookups. TryGetValue does one. And the bare indexer map["missing"] throws KeyNotFoundException. Missing that in an interview test case produces a written note in the feedback document. The note says things. They are not good things.

HashSet<T> shares the same O(1) average for add, contains, and remove. Set operations are linear in the size of the argument:

var a = new HashSet<int> { 1, 2, 3 };
var b = new HashSet<int> { 2, 3, 4 };
a.UnionWith(b);      // O(b.Count), iterates b, adds each to a
a.IntersectWith(b);  // O(a.Count), iterates a, removes anything not in b
a.ExceptWith(b);     // O(b.Count)
a.IsSubsetOf(b);     // O(a.Count)

The direction matters. a.IntersectWith(b) iterates a and checks each element against b. If b is a HashSet<T>, each check is O(1). If b is a List<T>, each check is O(b.Count) and your whole operation becomes O(a.Count * b.Count). Technically correct. Also, terrible.

Three Sorted Collections. One Will Ruin Your Interview.

C# gives you three sorted structures. They look interchangeable. They are not.

Sorted collections comparison

SortedDictionary: The One You Usually Want

Backed by a red-black tree. Every operation is O(log n), including insert and remove. This is your default when the collection changes frequently and needs to stay sorted.

var sd = new SortedDictionary<int, string>();
sd[5] = "five";         // O(log n)
sd.ContainsKey(5);      // O(log n)
sd.Remove(5);           // O(log n)
// Iterating gives keys in ascending order
foreach (var kv in sd) { /* O(n) total */ }

SortedList: Fast Lookup, Expensive Insert

Backed by two parallel sorted arrays: one for keys, one for values. Binary search gives O(log n) lookup. But inserting or removing anywhere except the end requires shifting: O(n). Most people discover this the same way, which is mid-interview, when they populate a SortedList in a loop and wonder why their supposedly O(log n) solution is timing out.

The case where SortedList wins: indexed access by position. sl.Keys[i] and sl.Values[i] are O(1). SortedDictionary has no indexed access at all. If the collection is mostly static after construction, or you need sorted order plus positional reads, SortedList is the right call.

var sl = new SortedList<int, string>();
sl.Add(3, "three");      // O(n), may shift
sl.ContainsKey(3);       // O(log n), binary search
sl.Keys[0];              // O(1), positional read, unique to SortedList
sl.IndexOfKey(3);        // O(log n)

SortedSet: The One Nobody Remembers Has a Range Method

Also a red-black tree, O(log n) for all basic operations. The feature nobody remembers: GetViewBetween(lo, hi) returns a live range view in O(log n + k) where k is the number of results.

var ss = new SortedSet<int> { 1, 3, 5, 7, 9 };
var view = ss.GetViewBetween(3, 7); // { 3, 5, 7 }
ss.Min;  // O(1)
ss.Max;  // O(1)

This makes SortedSet more useful than it looks for range-query problems. File it away.

Stacks and Queues Are Fine. The LinkedList Probably Isn't.

Both are array-backed. Their primary operations are O(1).

Stack<T>: push and pop from the same end. Queue<T>: enqueue to the tail, dequeue from the head. Peek on either is O(1). Searching is O(n). No indexed access on either.

var q = new Queue<int>();
q.Enqueue(1);   // O(1) amortized
q.Dequeue();    // O(1)
q.Peek();       // O(1), no remove

var s = new Stack<int>();
s.Push(1);      // O(1) amortized
s.Pop();        // O(1)
s.Peek();       // O(1)

LinkedList<T> has O(1) insert and delete when you hold a LinkedListNode<T>, but pays for it with pointer-chasing across the heap. Traversal is 5 to 10 times slower than an array on real hardware. Use it when you genuinely need O(1) interior deletes with a held reference, like in an LRU cache. Not otherwise. The .Count is O(1) and that's about all the good news.

PriorityQueue Showed Up in .NET 6. It Has Two Type Parameters.

PriorityQueue<TElement, TPriority> was added in .NET 6 and implements a min-heap by default. The two type parameters are separate, so priority and element are decoupled. Internally it uses a quaternary heap (4-ary tree) rather than binary, which improves cache performance.

var pq = new PriorityQueue<string, int>();
pq.Enqueue("slow task", 10);   // O(log n)
pq.Enqueue("urgent", 1);       // O(log n)
pq.Peek();                     // "urgent", O(1)
pq.Dequeue();                  // "urgent", O(log n)

Lowest priority value dequeues first. For a max-heap, pass a reversed comparer:

var maxPq = new PriorityQueue<string, int>(
    Comparer<int>.Create((a, b) => b.CompareTo(a))
);

There is no UpdatePriority or decrease-key. For Dijkstra or A*, the standard approach is lazy deletion: re-enqueue the node with the new priority and skip stale pops.

while (pq.Count > 0) {
    var (node, dist) = pq.Dequeue();
    if (dist > bestDist[node]) continue;  // stale entry, skip
    // process node
}

This adds O(E) extra entries in the worst case but is what interviewers expect to see.

Array.Sort Is Unstable. LINQ's OrderBy Isn't.

Array.Sort and List<T>.Sort are unstable. Both use introsort: quicksort by default, falls back to heapsort when recursion depth exceeds 2 * log₂(n), and switches to insertion sort for partitions of 16 or fewer elements. Worst case is guaranteed O(n log n).

LINQ's OrderBy is stable. Equal elements keep their original relative order. This matters when you sort by one key and the original ordering carries meaning.

int[] arr = { 3, 1, 4, 1, 5 };
Array.Sort(arr);                            // O(n log n), unstable, in-place
var stable = arr.OrderBy(x => x).ToArray(); // O(n log n), stable, new array

Array.BinarySearch on a sorted array returns the index if found, or the bitwise complement of the insertion point if not:

int idx = Array.BinarySearch(arr, 7);
if (idx < 0) {
    int insertAt = ~idx;  // where 7 would be inserted to preserve order
}

That bitwise complement idiom is a minor trap. Check idx == -1 for not-found and you will miss every other not-found result. Silent. Wrong.

Never subtract in a comparator. (a, b) => a - b overflows when a is near int.MaxValue and b is near int.MinValue. Use a.CompareTo(b) or int.Compare(a, b). Every language has this trap. C# is not special.

Four Traps That Feel Harmless Until They Aren't

Dictionary throws on missing key. The indexer map["x"] throws KeyNotFoundException. TryGetValue does not. Always handle the not-found case explicitly.

List<T>.Remove(item) is O(n). It scans for the item, then shifts. If you need O(1) removal by value, use a HashSet<T>. If you need O(1) removal by both value and order, you need a LinkedList<T> plus a Dictionary<T, LinkedListNode<T>>.

String concatenation in a loop is O(n²). Strings are immutable in C#. Each + allocates a new string and copies both operands. In a loop over thousands of elements you have written the slowest possible string-building code while the interviewer watches you write it.

// Wrong: O(n²)
string result = "";
foreach (var s in items) result += s;

// Right: O(n)
var sb = new StringBuilder();
foreach (var s in items) sb.Append(s);
string result = sb.ToString();

SortedList insert is O(n). The binary search for the insertion point is O(log n), but the array shift that follows is O(n). If you are inserting frequently, use SortedDictionary. This is also the entire reason the previous section exists.

Knowing the table is one thing. Explaining your choice out loud under interview pressure, while also writing correct code, is what SpaceComplexity trains. Voice-based mock interviews with rubric-graded feedback make the difference between knowing this and performing it.

For a broader look at which C# collections to reach for in different problem shapes, see C# for Coding Interviews. The parallel tables for Java and C++ are at Java Built-In Time Complexity and C++ STL Time Complexity. For the proof behind O(1) hash lookups, Hash Map Time Complexity covers the math.

Further Reading