What Big-O Doesn't Tell You: Constants, Cache and Measuring with BenchmarkDotNet

Version note: The code in this post was built and run with .NET 10 (C# 14); measurements were taken with BenchmarkDotNet 0.15.8 and tests with xUnit v3 4.0.2 on Apple M5 / macOS 27.0.1 / .NET 10.0.13.

Guess First

Bookstore's product page shows at most 10 books sorted by price in its "more from this author" box. There are three implementations: a hand-written insertion sort (O(n²)), OrderBy(b => b.Price).ToList() (O(n log n)) and Array.Sort with a comparison (O(n log n)). Which one is fastest? How far behind the other two does the O(n²) one fall?

Second question: summing a million ints. On an int[], a List<int> and a LinkedList<int>, all three O(n). How big is the difference between them? Over four posts in this series we talked about what Big-O tells you. This post talks about what it doesn't.

Constants Win at Small n

Big-O drops constants because they become negligible at large n. At small n, constants are all that's left. To see this I measured our own insertion sort and merge sort against .NET's Array.Sort on random arrays of 8, 16, 64 and 256 elements (each call first copies the source array, a cost that's the same for all three):

| Method    | N   | Mean         | Ratio |
|---------- |---- |-------------:|------:|
| Insertion | 8   |     7.744 ns |  1.00 |
| Merge     | 8   |    46.147 ns |  5.96 |
| ArraySort | 8   |     9.092 ns |  1.17 |
| Insertion | 16  |    27.700 ns |  1.00 |
| Merge     | 16  |   108.943 ns |  3.94 |
| ArraySort | 16  |    29.784 ns |  1.08 |
| Insertion | 64  |   385.940 ns |  1.00 |
| Merge     | 64  |   526.993 ns |  1.37 |
| ArraySort | 64  |   169.315 ns |  0.44 |
| Insertion | 256 | 5,881.215 ns |  1.00 |
| Merge     | 256 | 2,906.835 ns |  0.49 |
| ArraySort | 256 | 1,219.095 ns |  0.21 |

At 8 elements the O(n²) insertion sort is six times faster than the O(n log n) merge sort. It's still ahead at 64. Merge sort only pulls ahead at 256. The reason is constants: merge sort makes recursive calls at every level, copies into a buffer and back; insertion sort works in place, with predictable branches, in one tight loop.

.NET knows this, so Array.Sort is a hybrid. According to the Remarks section on Microsoft Learn, Array.Sort uses introsort: insertion sort if the partition is 16 elements or fewer, heapsort if the recursion depth exceeds 2·log n, quicksort otherwise. That's why Array.Sort takes almost the same time as our insertion sort in the 8- and 16-element rows: at that size it is running insertion sort. The details of introsort are in "Quick Sort, Introsort and Counting/Radix Sort: How .NET's Array.Sort Sorts" in the Algorithms and Data Structures series.

Cache and Pointer Chasing: List vs LinkedList

The measurement for the second guessing question:

| Method        | N       | Mean     | Ratio |
|-------------- |-------- |---------:|------:|
| ArraySum      | 1000000 | 256.1 us |  1.00 |
| ListSum       | 1000000 | 335.4 us |  1.31 |
| LinkedListSum | 1000000 | 969.4 us |  3.79 |

All three are O(n), all three visit a million elements once each. But LinkedList<int> is 3.8 times slower than the array. The difference comes from the hardware. The CPU (Central Processing Unit) reads memory not byte by byte but in blocks called cache lines, and it predicts the next access and fetches it ahead of time (prefetch). Because the array's elements sit next to each other in memory, one cache line carries several ints and the prefetcher has the next block ready. In a linked list every element is a separate node object; you only learn the address of the next one after reading the current node. This is called pointer chasing: every step waits for the previous one to finish, and prefetching gets much harder.

List<int> being 31 percent slower than the array is a different constant: the extra checks its enumerator does on every step, such as the version check that tells whether the list changed during iteration. Both are contiguous memory, both in the same growth class. Big-O sees none of these differences. Practical rules for choosing a collection are in "C# Queue, Stack, LinkedList and PriorityQueue: Collections That Work in Order" in the C# Collections series.

The Gap Between Average and Worst Case

In the first post of the series we said Dictionary's O(1) is an average case and left the worst case for this post. I added the same ISBN (International Standard Book Number) values to a dictionary with two different key types. One uses the normal GetHashCode the record generates, the other returns 42 for every key:

public sealed record GoodIsbn(string Value);

public sealed record BadIsbn(string Value)
{
    // Every key lands in the same bucket: lookups degrade to a linear scan
    public override int GetHashCode() => 42;
}

| Method   | N    | Mean          | Ratio  | Allocated |
|--------- |----- |--------------:|-------:|----------:|
| GoodHash | 1000 |      26.17 us |   1.00 | 123.18 KB |
| BadHash  | 1000 |   1,739.40 us |  66.57 | 123.18 KB |
| GoodHash | 2000 |      58.61 us |   1.00 |  257.4 KB |
| BadHash  | 2000 |   6,531.16 us | 111.67 |  257.4 KB |
| GoodHash | 4000 |     102.18 us |   1.00 | 304.28 KB |
| BadHash  | 4000 |  26,487.06 us | 259.23 | 304.26 KB |
| GoodHash | 8000 |     228.41 us |   1.00 | 628.33 KB |
| BadHash  | 8000 | 107,184.12 us | 469.39 | 628.27 KB |

Allocations are identical; the structure is the same, only the hash distribution differs. With a good hash, doubling n roughly doubles the time: n inserts, each O(1). With a bad hash, every insert walks the chain in the same bucket from start to end doing equality checks: n inserts, each O(n), O(n²) in total. The ratios show it: 1,739 → 6,531 → 26,487 → 107,184 microseconds, about 4 times at each step.

In real life you won't write a GetHashCode that returns 42. But hashes over a single low-variety property (such as a CategoryId shared by many books) or hashes tied to a mutable field partly produce the same effect. Attacker-controlled keys are a risk too: sending colliding keys to force a server into O(n²) is a known attack (hash flooding). .NET's string hash is computed with a random per-process seed, and a Dictionary with string keys switches to that randomized hash when the collision chain in a bucket gets long; when you write GetHashCode for your own key type, using HashCode.Combine is the easiest way to benefit from that protection.

The same gap exists in quicksort. I measured a naive quicksort that picks the first element as pivot on random and already sorted input:

| Method               | N    | Mean         | Ratio |
|--------------------- |----- |-------------:|------:|
| RandomInput          | 1000 |     9.057 us |  1.00 |
| SortedInput          | 1000 |   131.565 us | 14.53 |
| ArraySortSortedInput | 1000 |     2.131 us |  0.24 |
| RandomInput          | 2000 |    18.427 us |  1.00 |
| SortedInput          | 2000 |   498.132 us | 27.03 |
| ArraySortSortedInput | 2000 |     4.816 us |  0.26 |
| RandomInput          | 4000 |    56.603 us |  1.00 |
| SortedInput          | 4000 | 1,933.289 us | 34.17 |
| ArraySortSortedInput | 4000 |    10.557 us |  0.19 |

On sorted input the pivot is always the smallest element; every partition splits off just one element and the recursion goes n deep. The time grows 3.8 to 3.9 times with every doubling: O(n²). And since the recursion depth is n, a large enough sorted input also overflows the stack, as we saw in the third post of the series. Array.Sort finishes the same sorted input in 10 microseconds at 4,000 elements; introsort's pivot selection and depth limit exist for exactly this scenario. The input distribution matters as much as the algorithm: "the data already arrives almost sorted" is one of the most common distributions in production.

The Doubling Experiment: Estimating Complexity by Measuring

If you have code whose source you can't read or that's hard to analyze, you can estimate its complexity by measuring. The doubling ratio method from Sedgewick and Wayne's Algorithms (4th edition, §1.4) goes like this: double the input size at every step and look at the ratio of consecutive times. If the time is roughly a·nᵇ, the ratio approaches 2ᵇ. A ratio around 2 means linear, around 4 quadratic, around 8 cubic. For O(n log n) the ratio stays slightly above 2.

I wrote a small harness that does this. It measures 7 times at each size and takes the median:

// Sedgewick's doubling experiment: time(2n) / time(n) tends to 2^b for an n^b algorithm
public static void Doubling(string algorithm)
{
    // ... choose the algorithm and sizes
    foreach (var n in sizes)
    {
        var samples = new List<double>();
        for (var round = 0; round < 7; round++)
        {
            var items = (int[])source.Clone();
            var stopwatch = Stopwatch.StartNew();
            run(items);
            stopwatch.Stop();
            samples.Add(stopwatch.Elapsed.TotalMilliseconds);
        }
        var median = samples.Order().ElementAt(samples.Count / 2);
        var ratio = previous == 0 ? "" : $"{median / previous,6:F2}";
        Console.WriteLine($"{algorithm,-13} n={n,11:N0} median={median,10:F3} ms ratio={ratio}");
        previous = median;
    }
}

sum           n=  1,000,000 median=     0.276 ms ratio=
sum           n=  2,000,000 median=     0.563 ms ratio=  2.04
sum           n=  4,000,000 median=     1.087 ms ratio=  1.93
sum           n=  8,000,000 median=     2.284 ms ratio=  2.10
sort          n=  1,000,000 median=    47.682 ms ratio=
sort          n=  2,000,000 median=    94.058 ms ratio=  1.97
sort          n=  4,000,000 median=   215.456 ms ratio=  2.29
sort          n=  8,000,000 median=   415.670 ms ratio=  1.93
pairs         n=      1,000 median=     0.193 ms ratio=
pairs         n=      2,000 median=     0.711 ms ratio=  3.68
pairs         n=      4,000 median=     2.789 ms ratio=  3.92
pairs         n=      8,000 median=    11.387 ms ratio=  4.08

Summing gives ~2, the brute force that compares every pair ~4. For Array.Sort the ratios bounce between 1.93 and 2.29; n log n's theoretical ratio, only slightly above 2 (2.1 at n = 10⁶), can't be told apart from that noise. A doubling experiment cleanly separates linear from quadratic; telling n from n log n takes many more measurements and a much wider range of n.

In BenchmarkDotNet you do the same with [Params]: the BadHashBenchmarks and quicksort benchmarks above are already doubling experiments. BenchmarkDotNet's setup and result columns are covered in "Performance in C#: Allocations, Structs and Measuring with BenchmarkDotNet" in the Advanced C# series; what matters here is how you read the table. Divide the Mean column by the row above it; look at what the ratio is and whether it stays constant.

A Cold Stopwatch Misleads

Running the same harness on naive quicksort with sorted input produced this output:

quick-sorted  n=      1,000 median=     1.051 ms ratio=
quick-sorted  n=      2,000 median=     6.004 ms ratio=  5.71
quick-sorted  n=      4,000 median=    17.306 ms ratio=  2.88
quick-sorted  n=      8,000 median=     8.276 ms ratio=  0.48
quick-sorted  n=     16,000 median=    31.087 ms ratio=  3.76

8,000 elements came out twice as fast as 4,000. The algorithm didn't change; the measurement did. .NET's tiered compilation first compiles a method quickly with little optimization, then recompiles an optimized version in the background once it's called often. The first sizes of the run executed slow code, the later ones fast code. The same 1,000-element sort measured 1.05 milliseconds with Stopwatch and 0.13 milliseconds in BenchmarkDotNet. BenchmarkDotNet starting a separate process, running warmup iterations and taking a statistically sufficient number of measurements isn't decoration; it's there to weed out exactly this kind of error. If you measure by hand, at least run the same code a few times before measuring, and when you see inconsistent ratios, suspect your measurement first.

"The O(n log n) Solution Was Slower Than the O(n²) One"

Now the first guessing question. Sorting 10 books by price:

[Benchmark(Baseline = true)]
public Book InsertionSortByPrice()
{
    _source.CopyTo(_work, 0);
    Sorting.InsertionSortByPrice(_work);
    return _work[0];
}

[Benchmark]
public Book LinqOrderByToList() => _source.OrderBy(b => b.Price).ToList()[0];

[Benchmark]
public Book ArraySortWithComparison()
{
    _source.CopyTo(_work, 0);
    Array.Sort(_work, (a, b) => a.Price.CompareTo(b.Price));
    return _work[0];
}

| Method                  | Mean      | Ratio | Allocated |
|------------------------ |----------:|------:|----------:|
| InsertionSortByPrice    |  51.77 ns |  1.00 |         - |
| LinqOrderByToList       | 104.73 ns |  2.03 |     696 B |
| ArraySortWithComparison |  85.71 ns |  1.66 |         - |

The O(n²) insertion sort is twice as fast as LINQ's (Language Integrated Query) O(n log n) sort and 66 percent faster than Array.Sort with a comparison. It's a small example of why the code review comment "the O(n log n) one is better" isn't always right. What makes the difference lies outside Big-O:

• Allocation: OrderBy(...).ToList() allocates 696 bytes (the key array, the index map, the sorter objects, the result list). Insertion sort allocates nothing.
• Delegate calls: both the key selector and the comparison are an indirect call on every comparison. In the insertion sort the comparison is an inline decimal compare.
• Interface dispatch and generality: code that goes through IComparer<T> is slower than code where the JIT (Just-In-Time) compiler knows the concrete type and can inline. Handling a value type through object in a generic collection adds boxing on top.

This isn't advice to write insertion sorts. A 50-nanosecond difference on 10 elements is invisible next to the rest of the page; OrderBy is the right choice for readability. But the same difference becomes real on a hot path called millions of times a second. The decision is always made with a measurement.

In Production

This series boils down to one division of labor: analysis tells you which code will cause problems as it grows, measurement tells you which one is fast today. In code review, catch nested loops, Contains inside a loop and recursion whose depth comes from outside through analysis. When optimizing a hot path, don't guess: measure with BenchmarkDotNet and attach the result to the PR (pull request).

Think about the worst case with production's input. "Random input" is a lab assumption; in real systems data arrives sorted, the same key repeats, a single customer has ten thousand orders. If your own quicksort, hash function or cache key hasn't been measured on those distributions, consider it unmeasured.

Measure as a function of n. A single "12 ms" taken at one size says nothing; measurements taken at two or three sizes also reveal the growth class. That's why every benchmark in this post runs with at least two N values.

Common Pitfalls

Choosing by Big-O at small n. At 10 elements constants win; pick the readable option and measure if needed.

Taking the same Big-O for the same speed. Between an array and a linked list, both O(n), we measured a 3.8x difference.

Trusting the average case and ignoring the input. A bad hash or sorted input turns O(1) and O(n log n) into O(n) and O(n²).

Measuring cold code with Stopwatch. Tiered compilation, the GC (Garbage Collector) and CPU frequency make one-off measurements meaningless.

Looking at a single doubling ratio. One ratio can be noise; a trend is read from at least three points.

A Small Experiment

★☆☆ Add 32 and 128 to SmallSortBenchmarks. Find the n where your insertion sort and merge sort cross. Why might that number differ from .NET's threshold of 16?

★★☆ Change BadIsbn's GetHashCode to return Value.Length. Since every ISBN is 14 characters, what happens? Then return Value[^1] (the last character): how do the doubling ratios change with 10 distinct hash values?

★★★ Add a warmup phase to the doubling harness and measure naive quicksort on sorted input again. Do the ratios approach BenchmarkDotNet's 3.8–3.9? Then sort a 50,000-element sorted array on a 1.5 MB thread: what happens and why?

The Big-O and Complexity series ends here. You can now estimate the cost of code on paper, see the memory price of recursion and allocations, read amortized guarantees and test your estimate with BenchmarkDotNet. The real place to use these tools is the Algorithms and Data Structures series: there we'll write every data structure and algorithm ourselves, and every post will give its complexity in one line and link back to this series.