Why built-in calls need counting
One line of C# can hide a loop. When you estimate the time complexity of your code, a call such as list.Contains(x) costs as much as the loop inside it, not as much as one step. A solution that looks like a single loop can turn quadratic because of a call inside the loop body.
This lesson lists the costs of the built-in members you will use most. In every case n is the number of items in the collection the method is called on.
List<T>
| Operation | Cost | Why |
|---|---|---|
list[i], list.Count | O(1) | direct access to a stored slot |
list.Add(x) | O(1) amortized | appends at the end; occasional resizing is spread out |
list.Contains(x), list.IndexOf(x) | O(n) | scans item by item |
list.Insert(0, x) | O(n) | every later item shifts one place |
list.RemoveAt(0), list.Remove(x) | O(n) | items after the removed one shift; Remove also searches |
list.RemoveAt(list.Count - 1) | O(1) | nothing needs to shift |
list.Sort() | O(n log n) | comparison sort |
list.Reverse() | O(n) | swaps items in place |
The difference between the two ends matters. Adding or removing at the end is cheap, while adding or removing at the front moves every other item. Building a list of n items by inserting each one at index 0 does about n²/2 item moves in total.
Dictionary, HashSet, Stack and Queue
| Operation | Cost |
|---|---|
dict[key], dict.ContainsKey(key), dict.TryGetValue(...) | O(1) on average |
| adding or removing a key | O(1) on average |
set.Add(x), set.Contains(x), set.Remove(x) | O(1) on average |
stack.Push, stack.Pop | O(1) |
queue.Enqueue, queue.Dequeue | O(1) |
dict.Keys or dict.Values traversed in a loop | O(n) |
"On average" matters for the hash-based types. They compute a number from the key to jump to a spot, and a pile of unlucky collisions could slow a lookup, but in normal use the cost is constant. If a Dictionary is indexed with a key that isn't there, it throws KeyNotFoundException. Use TryGetValue or ContainsKey when the key may be missing.
These types are the usual cure for a hidden linear scan. Checking membership in a List<int> costs O(n) per check. Putting the same values into a HashSet<int> first brings each check down to O(1) on average.
LINQ and strings in a loop
LINQ methods read like one-liners, but each one still does the work behind the scenes:
Sum(),Max(),Min(),Contains(x)andToList()on a sequence areO(n).OrderBy(...)isO(n log n), since it sorts.
String concatenation has a trap. Strings are immutable, so s += "x" builds a new string and copies the old content. Doing that in a loop of n passes copies about n²/2 characters in total. A StringBuilder keeps a growing buffer, so each Append is O(1) on average, and the whole loop is O(n):
var sb = new StringBuilder();
for (int i = 0; i < 5; i++) {
sb.Append(i);
}
Console.WriteLine(sb.ToString()); // 01234
This needs using System.Text;. For a handful of concatenations, plain + is fine.
LINQ queries such as Where and Select are lazy: they do no work when you write them, only when something enumerates the result. If you enumerate the same query twice, for example with two foreach loops, the work is done twice. Calling ToList() once and reusing the list avoids that.
Counting a call inside a loop
Multiply the cost of the call by the number of passes:
static int CountCommon(List<int> a, List<int> b) {
int count = 0;
foreach (int x in a) {
if (b.Contains(x)) {
count++;
}
}
return count;
}
The loop runs once per item of a, and b.Contains(x) scans b. If both lists have n items, that is O(n²). Building a HashSet<int> from b once, which costs O(n), and calling Contains on the set makes the whole method O(n) on average.
Choosing a collection by what you do most
The table of costs turns into a simple rule of thumb:
- If you mostly read by position or append at the end, use a
List<T>or an array. - If you mostly ask "is this value here?" or "what goes with this key?", use a
HashSet<T>or aDictionary<K, V>. - If you add at one end and take from the other, use a
Queue<T>. For last in, first out, use aStack<T>.
Each of these has costs you pay in return. A set doesn't keep items in positions, and a list can't answer membership questions quickly. Picking the type that matches your most frequent operation is often the whole optimization.
Key takeaways
- Index access,
Countand appending to a list's end are cheap. - Searching a list, inserting at the front and removing from the front are
O(n). - Sorting costs
O(n log n). - Dictionaries and sets give
O(1)average lookups, so they replace repeated list scans. - Always count the cost of a call inside a loop, and use
StringBuilderto build strings in loops.