The C# Angle: Collection Costs, LINQ Costs, Strings and Span in Coding Interviews

Learning outcome

You can spot the C# calls that silently change a solution's complexity (List.Contains, List.Insert(0), RemoveAt(0), ElementAt on a sequence, string +=), choose the collection that matches the access pattern, and use Span<T> and StringBuilder to avoid allocations. You can also show that you verify LINQ costs instead of guessing.

Intuition

Interviewers grade the algorithm, but in C# the algorithm hides inside library calls. One Contains on a List<T> inside a loop turns O(n) into O(n²). The fix is rarely a new algorithm; it is the right collection. For the full table of collection costs, keep the .NET Collections Big-O Cheat Sheet open; this lesson shows the costs that matter most in coding rounds, measured.

flowchart TD
    Q{"What does the loop do?"} -->|"membership test"| H["HashSet / Dictionary: O(1) avg"]
    Q -->|"take from the front"| QQ["Queue<T>: O(1)"]
    Q -->|"take smallest/largest"| P["PriorityQueue: O(log n)"]
    Q -->|"index access"| L["List<T> / T[]: O(1); List.Add: amortized O(1)"]
    Q -->|"build a string"| S["StringBuilder"]
    Q -->|"slice without copying"| SP["Span<T> / ReadOnlySpan<char>"]

Deep dive

• Collections used in this course:
  • T[] and List<T>: O(1) indexing. List.Add is amortized O(1); arrays have fixed length, so growing one requires allocating and copying. Inserting or removing at the front of a list shifts elements: O(n) per call.
  • Dictionary<TKey,TValue> and HashSet<T>: O(1) average lookup, add and remove. Enumeration order is not guaranteed by the documentation.
  • Stack<T> and Queue<T>: O(1) push/pop and enqueue/dequeue (amortized when they grow). Queue<T> is a circular buffer, so dequeuing does not shift elements.
  • PriorityQueue<TElement,TPriority> (.NET 6+): a min-heap; O(log n) enqueue and dequeue, O(1) peek (Lesson 14).
  • SortedSet<T> and SortedDictionary<TKey,TValue>: balanced trees, O(log n) per operation with ordering and ranges (Lesson 11).
  • LinkedList<T>: O(1) insert/remove when you hold the node, but one heap allocation per node (Lesson 8 measures it).
• LINQ in algorithms:
  • LINQ is fine for building inputs and for one-pass work outside hot loops. Inside a loop, each call is a full pass unless the operator has a fast path.
  • ElementAt(i) on a plain IEnumerable<T> (for example a yield method) walks from the start every time; on an IList<T> it indexes directly.
  • Count() enumerates when neither a collection count nor an internal LINQ counting fast path applies; Count on a List<T> is O(1).
  • Some combinations are optimized internally. OrderBy(x).First() does not sort in current .NET: it scans once for the minimum. Materializing the sort (ToArray(), ToList(), or enumerating it) does sort. Do not memorize which combinations are special: measure, or write the loop. The Time and Space Complexity in LINQ course covers each operator.
• Strings:
  • string is immutable. s += c in a loop allocates a new string each time and copies the old one: O(n²) time and allocation in total.
  • StringBuilder appends into a growing buffer: amortized O(1) per append.
  • Substring allocates a copy. AsSpan(start, length) and range slicing on a ReadOnlySpan<char> do not allocate.
• Span<T> in coding rounds:
  • Span<T> / ReadOnlySpan<T> give a view over an array, a string or stackalloc memory. Slicing (a[..k]) is O(1) and allocation-free.
  • Useful helpers: span.Reverse(), span.Sort(), span.IndexOf, int.Parse(ReadOnlySpan<char>), and in .NET 9+ span.Split(',') which yields Range values.
  • stackalloc int[26] gives a fixed-size counting array with no heap allocation (Lessons 3 and 6).
  • Limits: a Span<T> cannot be stored in a field of a class, captured in a lambda, or used across await.

Code example: measured costs

// L02: the C# costs that change a solution's complexity: collection choice, LINQ in loops,
// string building and Span slicing. Allocations are measured with GC.GetAllocatedBytesForCurrentThread.

static long Alloc(Action a) { a(); long b = GC.GetAllocatedBytesForCurrentThread(); a(); return GC.GetAllocatedBytesForCurrentThread() - b; }

// 1. Membership test inside a loop: List.Contains is O(n) per call, HashSet.Contains O(1) average.
int n = 20_000;
var list = Enumerable.Range(0, n).ToList();
var set = new HashSet<int>(list);
Big.Time("List.Contains x n (O(n^2) total)", [10_000, 20_000, 40_000], m => { var l = Enumerable.Range(0, m).ToList(); return () => { int c = 0; for (int i = 0; i < m; i++) if (l.Contains(m - 1 - i)) c++; }; });
Big.Time("HashSet.Contains x n (O(n) total)", [10_000, 20_000, 40_000], m => { var s = new HashSet<int>(Enumerable.Range(0, m)); return () => { int c = 0; for (int i = 0; i < m; i++) if (s.Contains(m - 1 - i)) c++; }; });

// 2. List.Insert(0, x) shifts every element: n inserts cost O(n^2). Add is amortized O(1).
Big.Time("List.Insert(0) x n", [10_000, 20_000, 40_000], m => () => { var l = new List<int>(); for (int i = 0; i < m; i++) l.Insert(0, i); });
Big.Time("List.Add x n", [10_000, 20_000, 40_000], m => () => { var l = new List<int>(); for (int i = 0; i < m; i++) l.Add(i); });

// 3. LINQ inside a loop. ElementAt on this yield sequence walks from the start each time.
IEnumerable<int> Seq(int m) { for (int i = 0; i < m; i++) yield return i; }
static long SumByElementAt(IEnumerable<int> s, int m) { long t = 0; for (int i = 0; i < m; i++) t += s.ElementAt(i); return t; }
Check.Eq("ElementAt loop sum n=1000", SumByElementAt(Seq(1000), 1000), 499_500L);
Big.Time("ElementAt(i) in a loop over a yield sequence", [2_000, 4_000, 8_000], m => { var s = Seq(m); return () => SumByElementAt(s, m); });

// Verify LINQ costs instead of assuming. OrderBy(x).First() is special-cased by .NET (a single
// O(n) scan, no sort), but materializing the sort (ToArray()[0]) buffers and sorts: O(n log n), O(n) space.
var data = Big.RandomArray(100_000, 1_000_000);
Check.Eq("OrderBy().First() == Min()", data.OrderBy(x => x).First(), data.Min());
Console.WriteLine($"alloc OrderBy(x).First():      {Alloc(() => data.OrderBy(x => x).First()):N0} bytes");
Console.WriteLine($"alloc OrderBy(x).ToArray()[0]: {Alloc(() => _ = data.OrderBy(x => x).ToArray()[0]):N0} bytes");
Console.WriteLine($"alloc Min():                   {Alloc(() => data.Min()):N0} bytes");
Big.Time("OrderBy(x).First()", [200_000, 400_000, 800_000], m => { var d = Big.RandomArray(m, 1_000_000); return () => d.OrderBy(x => x).First(); });
Big.Time("OrderBy(x).ToArray()[0]", [200_000, 400_000, 800_000], m => { var d = Big.RandomArray(m, 1_000_000); return () => _ = d.OrderBy(x => x).ToArray()[0]; });

// 4. Strings are immutable: += in a loop copies the whole string every time.
static string Concat(int m) { string s = ""; for (int i = 0; i < m; i++) s += 'x'; return s; }
static string Builder(int m) { var sb = new System.Text.StringBuilder(); for (int i = 0; i < m; i++) sb.Append('x'); return sb.ToString(); }
Check.Eq("same result", Concat(2000) == Builder(2000), true);
foreach (int m in new[] { 2_000, 4_000 })
    Console.WriteLine($"m={m:N0}: += allocates {Alloc(() => Concat(m)):N0} bytes, StringBuilder {Alloc(() => Builder(m)):N0} bytes");

// 5. Substring allocates a new string; AsSpan slices without copying.
string csv = string.Join(",", Enumerable.Range(0, 1000));
static int SumSubstring(string s) { int t = 0, start = 0; for (int i = 0; i <= s.Length; i++) if (i == s.Length || s[i] == ',') { t += int.Parse(s.Substring(start, i - start)); start = i + 1; } return t; }
static int SumSpan(string s) { int t = 0; var r = s.AsSpan(); foreach (var part in r.Split(',')) t += int.Parse(r[part]); return t; }
Check.Eq("Substring sum", SumSubstring(csv), 499_500);
Check.Eq("Span sum", SumSpan(csv), 499_500);
Console.WriteLine($"alloc Substring parse: {Alloc(() => SumSubstring(csv)):N0} bytes; Span parse: {Alloc(() => SumSpan(csv)):N0} bytes");
Check.Summary();

Output (.NET 10, Release, tiered compilation off)

time growth (median of 5, varies per run): List.Contains x n (O(n^2) total)
  n=       10,000      7.550 ms
  n=       20,000     32.192 ms  x4.3
  n=       40,000    131.125 ms  x4.1
time growth (median of 5, varies per run): HashSet.Contains x n (O(n) total)
  n=       10,000      0.035 ms
  n=       20,000      0.070 ms  x2.0
  n=       40,000      0.137 ms  x2.0
time growth (median of 5, varies per run): List.Insert(0) x n
  n=       10,000      1.376 ms
  n=       20,000     11.395 ms  x8.3
  n=       40,000     55.524 ms  x4.9
time growth (median of 5, varies per run): List.Add x n
  n=       10,000      0.042 ms
  n=       20,000      0.096 ms  x2.3
  n=       40,000      0.102 ms  x1.1
PASS ElementAt loop sum n=1000 -> 499500
time growth (median of 5, varies per run): ElementAt(i) in a loop over a yield sequence
  n=        2,000      4.640 ms
  n=        4,000     18.399 ms  x4.0
  n=        8,000     74.300 ms  x4.0
PASS OrderBy().First() == Min() -> 2
alloc OrderBy(x).First():      120 bytes
alloc OrderBy(x).ToArray()[0]: 1,600,304 bytes
alloc Min():                   0 bytes
time growth (median of 5, varies per run): OrderBy(x).First()
  n=      200,000      1.516 ms
  n=      400,000      3.234 ms  x2.1
  n=      800,000      6.517 ms  x2.0
time growth (median of 5, varies per run): OrderBy(x).ToArray()[0]
  n=      200,000     43.583 ms
  n=      400,000     91.696 ms  x2.1
  n=      800,000    203.078 ms  x2.2
PASS same result -> True
m=2,000: += allocates 4,051,976 bytes, StringBuilder 8,696 bytes
m=4,000: += allocates 16,103,976 bytes, StringBuilder 16,864 bytes
PASS Substring sum -> 499500
PASS Span sum -> 499500
alloc Substring parse: 31,920 bytes; Span parse: 0 bytes
tests: 5 passed, 0 failed

Code walkthrough

• List.Contains inside a loop of n: going from 10,000 to 40,000 the time went x4.3 then x4.1, the O(n²) signature. The HashSet.Contains loop went x2.0 and x2.0: O(n).
• n calls to List.Insert(0, i) grew x8.3 then x4.9; every insert shifts all existing elements. n calls to List.Add took well under a millisecond; at that scale the ratios (x2.3, x1.1) are measurement noise, which is why tiny timings prove nothing.
• ElementAt(i) over a yield sequence went x4.0 and x4.0 for 2,000 → 8,000: O(n²), because each call restarts the iterator. The test confirms the sum is still correct (499500): the bug is cost, not correctness.
• OrderBy(x).First() allocated 120 bytes and grew x2.1 then x2.0: .NET runs it as a single scan. OrderBy(x).ToArray()[0] allocated 1,600,304 bytes for 100,000 ints (the sort buffers) and was far slower at every size. Min() allocated 0 bytes.
• String building: for 2,000 characters += allocated 4,051,976 bytes versus 8,696 for StringBuilder. Doubling to 4,000 characters made += allocate 16,103,976 bytes (about x4, quadratic) while StringBuilder roughly doubled to 16,864.
• Parsing 1,000 comma-separated numbers: Substring allocated 31,920 bytes; the Span version with Split and int.Parse(ReadOnlySpan<char>) allocated 0 bytes.

Complexity

Failure modes

• if (!list.Contains(x)) list.Add(x) to build a distinct list: O(n²). Use a HashSet<T>.
• list.RemoveAt(0) as a queue: O(n) per dequeue.
• Re-enumerating a lazy LINQ query inside a loop (query.Count() each iteration).
• string += in a loop to build output.
• Assuming a LINQ chain sorts or buffers (or does not) without checking. Some chains have fast paths; most do not.
• Storing a Span<T> in a class field or capturing it in a lambda: the compiler rejects it. Use Memory<T> or indices.

Interview angle

"Your solution is O(n), but it calls result.Contains(x) in the loop." Answer: "That is a List<T>, so Contains is a linear scan and the loop is O(n²). I will keep a HashSet<int> alongside it for membership checks; that makes the loop O(n) average with O(n) extra space. If order does not matter, the HashSet alone is enough."

Practice questions

1. Why is OrderBy(x => x).ToArray()[0] worse than Min()?

Answer: It sorts the whole sequence, O(n log n) time and O(n) buffers; Min() is one O(n) pass with O(1) space.

2. What does s += c cost in a loop of n characters?

Answer: O(n²) time and allocation; each step copies the whole string.

3. Which collection replaces List<T> used as a FIFO queue?

Answer: Queue<T>: O(1) enqueue and dequeue.

4. Can you keep a Span<char> in a class field?

Answer: No. Span<T> is a ref struct; use Memory<T> or store start/length indices.

Revision checklist

• Membership in a loop: HashSet/Dictionary, never List.Contains.
• Front removal: Queue<T>, never RemoveAt(0).
• Build strings with StringBuilder; slice with spans.
• LINQ inside loops: each call is a pass unless proven otherwise.
• Small timings are noise; compare growth.

Related on TechInterviewNotes

• Cheat sheet: .NET Collections Big-O Cheat Sheet
• Course: Time and Space Complexity in LINQ
• Lesson: Allocation-free alternatives: Span, ArrayPool and loops
• Library: Choosing between StringBuilder and string concatenation in C#
• Library: Allocation-aware parsing with ReadOnlySpan<char>

References

• Collections and data structures
• Memory<T> and Span<T> usage guidelines
• StringBuilder class