Counting steps in real code
Work out the Big-O of real C# by looking at loop shapes, spot the hidden loops inside .NET methods, and know what input sizes each growth rate can handle.
| Code shape | Rule | Result |
|---|---|---|
O(1) | ||
O(n) | ||
O(n) + O(n) = O(n) | ||
O(n) × O(n) = O(n²) | ||
O(log n) | ||
Inner loops that depend on the outer loop
i + 1, it runs n−1 times, then n−2, then n−3… down to 0. That adds up to n(n−1)/2, about half of n². Half is a constant, so it is still O(n²). This shape appears whenever you compare every pair of items once.
Hidden loops in .NET methods
// Looks like one loop, but List.Contains is another loop inside → O(n²)static bool HasDuplicateSlow(List<string> ids){ var seen = new List<string>(); foreach (var id in ids) { if (seen.Contains(id)) return true; // O(n) scan every time! seen.Add(id); } return false;} // HashSet lookups take about one step each → O(n)static bool HasDuplicateFast(List<string> ids){ var seen = new HashSet<string>(); foreach (var id in ids) { if (!seen.Add(id)) return true; // Add returns false if already there } return false;}| Operation | Cost |
|---|---|
list[i], array[i], list.Count | O(1) |
list.Add(x) | O(1) on average (amortised; see Dynamic arrays) |
list.Contains(x), IndexOf, Remove(x) | O(n): scans the list |
list.Insert(0, x), list.RemoveAt(0) | O(n): shifts every element |
dict[key], TryGetValue, ContainsKey, HashSet.Contains | O(1) on average |
Array.Sort, list.Sort, LINQ OrderBy | O(n log n) |
Where, Select, Any, First, Count() | O(n) when enumerated |
.ToList(), .ToArray() | O(n) time and O(n) memory |
s = s + x in a loop (strings) | O(n²) in total: copies the whole string each time. Use StringBuilder. |
What input size can each growth rate handle?
| Largest n for ~1 second | Algorithm must be |
|---|---|
O(n!) | |
O(2ⁿ) | |
O(n³) | |
O(n²) | |
O(n log n) | |
O(n) | |
O(log n) or O(1) |
a also appear in b. Give its Big-O, then rewrite it to be O(a + b).
Show a hint
Show the solution
// Original: O(a × b) because List.Contains scans b each timestatic int CommonSlow(List<int> a, List<int> b){ int count = 0; foreach (int x in a) if (b.Contains(x)) count++; return count;} // Faster: O(a + b)static int CommonFast(List<int> a, List<int> b){ var inB = new HashSet<int>(b); // O(b), once int count = 0; foreach (int x in a) // O(a) if (inB.Contains(x)) count++; // O(1) each return count;} Console.WriteLine($"Common: {CommonFast([1, 2, 3, 4], [3, 4, 5])}");Common: 2
Remember
Loops one after another add; loops inside loops multiply; halving loops are O(log n). A method call inside a loop multiplies the loop by the cost of the call. List.Contains,IndexOf,Insert(0, …)and LINQ queries are hidden O(n) loops.About 100 million simple steps per second: O(n²) is fine for 10,000 items, not for a million.