Deriving Time Complexity from Code: Loops, log n and Recursion

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.

Guess First

Bookstore's end-of-day report writes the customer's name next to every order. Someone wrote the code years ago and it still works:

public static List<OrderLine> Naive(List<Order> orders, List<Customer> customers)
{
    var lines = new List<OrderLine>(orders.Count);
    foreach (var order in orders)
    {
        var customer = customers.First(c => c.Id == order.CustomerId);
        lines.Add(new OrderLine(order.Id, customer.Name, order.Total));
    }
    return lines;
}

With 1,000 orders and 1,000 customers this method finishes in 220 microseconds. The company is growing; the same report will run with 10,000 orders and 10,000 customers. Does the time go up 10 times, 100 times, or something else? There's only one loop in the code; does that affect your answer?

In the previous post we built the language of Big-O but counted steps by hand. In this post we'll learn to read that count from the code. At the end we'll answer this question both on paper and with BenchmarkDotNet.

Sequential Blocks Add, Nested Loops Multiply

There are two basic rules for deriving complexity from code. Blocks that run one after another add up; blocks that run one inside another multiply. Let's write four loop shapes and count how many times each inner body runs:

public static class LoopShapes
{
    // Two loops one after the other: n + n = 2n steps -> O(n)
    public static long Sequential(int n)
    {
        long steps = 0;
        for (var i = 0; i < n; i++) steps++;
        for (var j = 0; j < n; j++) steps++;
        return steps;
    }

    // A loop inside a loop: n * n steps -> O(n^2)
    public static long Nested(int n)
    {
        long steps = 0;
        for (var i = 0; i < n; i++)
            for (var j = 0; j < n; j++)
                steps++;
        return steps;
    }

    // Inner loop depends on the outer one: n(n-1)/2 steps -> still O(n^2)
    public static long Triangular(int n)
    {
        long steps = 0;
        for (var i = 0; i < n; i++)
            for (var j = 0; j < i; j++)
                steps++;
        return steps;
    }

    // The remaining range halves every step -> O(log n)
    public static long Halving(int n)
    {
        long steps = 0;
        for (var remaining = n; remaining > 1; remaining /= 2) steps++;
        return steps;
    }
}

Real output for n = 1,000 and n = 2,000:

n= 1000: sequential=    2,000 nested=  1,000,000 triangular=    499,500 halving=  9
n= 2000: sequential=    4,000 nested=  4,000,000 triangular=  1,999,000 halving= 10

When n doubled, Sequential doubled and Nested quadrupled. The interesting one is Triangular. Because the inner loop is written as j < i, it doesn't run at all on the first pass and runs n − 1 times on the last. The total is 0 + 1 + … + (n − 1) = n(n − 1)/2. That's roughly half of Nested; but half is a constant factor, the n² term stays. When n doubled it quadrupled too: Θ(n²).

This shape shows up in real code all the time. A duplicate check written as "compare each book with the books after it", a fraud check written as "compare each order with the previous orders": all triangular loops. "The inner loop gets shorter every time, so it isn't n²" is one of the most common analysis mistakes.

The rules have one more consequence: in a sum, the dominant term wins. If a method first sorts a list (O(n log n)) and then walks it once (O(n)), the total is O(n log n + n) = O(n log n). Optimizing the fast part doesn't change the complexity unless you speed up the slow part.

A Loop That Halves Every Step: log n

In Halving, doubling n added just one step. The loop variable doesn't grow by a fixed amount, it shrinks by a fixed ratio. Start from n and halve it k times and you're left with n/2ᵏ; the loop ends when that reaches 1, so k = log₂ n. For 1,000 that's ⌊log₂ 1,000⌋ = 9, for 2,000 it's 10.

You'll see this shape in binary search, in the height of balanced trees, in pulling the digits out of a number one at a time (dividing by 10 each step). The base of the logarithm doesn't matter in Big-O: log₁₀ n = log₂ n / log₂ 10, and the difference is a constant factor. That's why we don't write the base in O(log n).

A small warning: if the loop variable grows by multiplication (i *= 2) that's log n too. But if it grows by i += 2 it takes n/2 steps and is O(n). To tell whether a loop is log n, look at how the variable changes: addition and subtraction are linear, multiplication and division are logarithmic.

Recursion: Writing a Recurrence and the Recursion Tree

You can't find the cost of a recursive function by counting loops; you write a recurrence instead. A recurrence is an equation that expresses T(n) in terms of T on smaller inputs. Three classic examples:

public static class Recursion
{
    // T(n) = T(n-1) + T(n-2) + O(1) -> O(phi^n), roughly O(1.618^n)
    public static long NaiveFibonacci(int n, ref long calls)
    {
        calls++;
        return n < 2 ? n : NaiveFibonacci(n - 1, ref calls) + NaiveFibonacci(n - 2, ref calls);
    }

    // T(n) = T(n/2) + O(1) -> O(log n); returns the recursion depth it reached
    public static int BinarySearchDepth(int[] sorted, int target, int low, int high, int depth = 1)
    {
        if (low > high) return depth;
        var mid = low + (high - low) / 2;
        if (sorted[mid] == target) return depth;
        return sorted[mid] < target
            ? BinarySearchDepth(sorted, target, mid + 1, high, depth + 1)
            : BinarySearchDepth(sorted, target, low, mid - 1, depth + 1);
    }

    // T(n) = 2T(n/2) + O(n) -> O(n log n)
    public static void MergeSort(int[] items, int[] buffer, int low, int high, ref long comparisons)
    {
        if (high - low < 1) return;
        var mid = low + (high - low) / 2;
        MergeSort(items, buffer, low, mid, ref comparisons);
        MergeSort(items, buffer, mid + 1, high, ref comparisons);

        int left = low, right = mid + 1, k = low;
        while (left <= mid && right <= high)
        {
            comparisons++;
            buffer[k++] = items[left] <= items[right] ? items[left++] : items[right++];
        }
        while (left <= mid) buffer[k++] = items[left++];
        while (right <= high) buffer[k++] = items[right++];
        Array.Copy(buffer, low, items, low, high - low + 1);
    }
}

Real output:

fib(20) =   6,765  calls =      21,891
fib(25) =  75,025  calls =     242,785
fib(30) = 832,040  calls =   2,692,537
n=    1,000: binary search depth = 10  merge sort comparisons =      8,782  n*log2(n) =      9,966
n=1,000,000: binary search depth = 20  merge sort comparisons = 18,849,374  n*log2(n) = 19,931,569

The most intuitive way to solve a recurrence is to draw a recursion tree: the first call at the root, the calls it makes below it, and next to every node the work that call does outside the recursion. The total cost is the sum over all nodes.

In naive Fibonacci every node opens two children and the tree goes n levels deep; roughly 2ⁿ nodes. The exact count is a bit lower: the number of calls is 2·F(n+1) − 1, so 2,692,537 for fib(30). I verified that with an xUnit test as well. Every step of 5 multiplies the call count by about 11 (1.618⁵ ≈ 11.1). If adding 5 to n multiplies the work by eleven, the algorithm is exponential. Because it solves the same subproblems over and over, memoization brings it down to O(n); we'll do that in the dynamic programming post of the Algorithms and Data Structures series.

In binary search every call opens a single child and halves the problem: the tree is a chain, log₂ n deep. The output shows 10 for 1,000 and 20 for 1,000,000. In merge sort the problem splits in two at every level, the tree has log₂ n levels and the merge work on each level adds up to n. The total is n · log₂ n. The measured comparison count (18.8 million) is just below n log₂ n (19.9 million); when one side runs out during a merge, the remaining elements are copied without comparisons.

The Master Theorem: Three Cases, Intuitively

For recurrences of the form "split the problem into a parts, each of size n/b, with f(n) work to split and combine" we write T(n) = a·T(n/b) + f(n). The master theorem solves most of them at a glance. Without going into the proof, the idea is this: the total work at the leaves of the recursion tree is n^(log_b a). You compare that with the work at the root, f(n).

In the third case CLRS (Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein) also requires a "regularity condition"; the f(n)s you'll meet in real life satisfy it. The important limit: the master theorem is only for "divide by b" recurrences. Recurrences like naive Fibonacci's "go down to n − 1 and n − 2" don't fit; for those you draw a recursion tree or expand the recurrence.

Hidden Costs: Loops in a Single Line

The code in the guessing section has a single foreach, but customers.First(...) is a loop inside that starts at the beginning of the list and walks until it finds a match. Library methods, LINQ (Language Integrated Query) operators in particular, hide their complexity; you have to count them too. I measured three common cases in the same demo (code trimmed):

// 1) Count() and ElementAt() on a lazy query inside a loop
var books = CatalogFactory.Create(2_000);
var predicateCalls = 0;
IEnumerable<Book> cheap = books.Where(b => { predicateCalls++; return b.Price < 50m; });
decimal total = 0;
for (var i = 0; i < cheap.Count(); i++)
{
    total += cheap.ElementAt(i).Price;
}

// 2) string += copies the whole string every time
var csv = "";
for (var i = 0; i < n; i++) csv += "978-0000000001;";

// 3) OrderBy(...).First() vs MinBy: count comparisons
_ = prices.OrderBy(p => p, comparer).First();
_ = prices.OrderBy(p => p, comparer).ToList()[0];
_ = prices.MinBy(p => p, comparer);

Real output:

lazy query in a loop : predicate calls = 2,692,550
materialized once    : predicate calls = 2,000
n= 1000: += allocated   15,039,944 bytes   StringBuilder    63,200 bytes
n= 2000: += allocated   60,079,944 bytes   StringBuilder   125,344 bytes
n= 4000: += allocated  240,159,944 bytes   StringBuilder   249,632 bytes
OrderBy().First()      comparisons = 999
OrderBy().ToList()[0]  comparisons = 10,917
MinBy()                comparisons = 999

In the first case cheap isn't a list, it's a query. Because of deferred execution, every Count() call in the loop condition filters all 2,000 books from scratch, and ElementAt(i) runs the filter again up to the i-th match. The result: 2.7 million predicate calls for a 2,000-book list, i.e. O(n²). Materializing the query once with ToList() brings the number down to 2,000. The docs for ElementAt say it uses the indexer when the source is an IList<T>; the result of a Where is not an IList<T>. The mechanics of deferred execution are in "LINQ Deferred Execution: When Does a Query Run? IEnumerable and IQueryable" in the C# LINQ series.

In the second case, doubling n quadruples the allocations of +=: 15 MB, 60 MB, 240 MB. Because strings are immutable, every += copies all the content so far into a new string; the total number of copied characters is 15 + 30 + … + 15n ≈ 7.5n², i.e. O(n²). StringBuilder grows linearly. The details are in "Strings in C#: Interpolation, StringBuilder and the Turkish I Trap" in the C# Fundamentals series.

The third case is a surprise. On paper OrderBy().First() sorts first (O(n log n)) and then takes the first element. But the measurement shows 999 comparisons; exactly as many as MinBy, i.e. O(n). The reason is in the dotnet/runtime source code: the TryGetFirst implementation of OrderedEnumerable doesn't sort, it walks the list once and finds the smallest element. Write ToList()[0] and the shortcut doesn't apply, so a real sort makes 10,917 comparisons. The lesson: sometimes complexity is written in the implementation rather than the docs, and it can change between versions. Using MinBy, which states your intent, is both readable and means not relying on an optimization.

The first place to look for the complexity of library methods is the Remarks section on Microsoft Learn. For List<T>.Contains it says "performs a linear search, O(n)"; for List<T>.Add it says "O(1) if Count is less than Capacity, otherwise O(n)." Why the latter still counts as O(1) is the topic of the fourth post in the series.

Matching Orders to Customers: From O(n·m) to O(n+m)

Back to the code from the guessing section. The outer loop walks n orders. The First inside looks at m/2 customers on average. The total is O(n·m). When n and m both grow 10 times the expected increase is 100 times. The fix is to put the customers into a Dictionary once:

// Build the index once (O(m)), then one lookup per order (O(n)): O(n + m)
public static List<OrderLine> WithDictionary(List<Order> orders, List<Customer> customers)
{
    var byId = customers.ToDictionary(c => c.Id);
    var lines = new List<OrderLine>(orders.Count);
    foreach (var order in orders)
    {
        var customer = byId[order.CustomerId];
        lines.Add(new OrderLine(order.Id, customer.Name, order.Total));
    }
    return lines;
}

An xUnit test verifies that both versions produce the same lines (5,000 orders, 1,200 customers, Assert.Equal(expected, actual)). The measurement (Apple M5, .NET 10.0.13; table trimmed):

| Method         | N     | Mean          | Ratio | Allocated |
|--------------- |------ |--------------:|------:|----------:|
| Naive          | 1000  |    220.713 us |  1.00 | 140.68 KB |
| WithDictionary | 1000  |      8.286 us |  0.04 |  84.95 KB |
| Naive          | 10000 | 32,968.864 us | 1.000 | 1406.3 KB |
| WithDictionary | 10000 |    151.117 us | 0.005 | 823.28 KB |

The naive version got 149 times slower on 10 times the data. Theory says 100 times; the rest most likely comes from memory access: every comparison follows a pointer to a Customer object and 10,000 objects no longer fit in the L1 (level 1) cache; on top of that there's a delegate call per element. The dictionary version got 18 times slower, above the expected 10, because at this size the dictionary's internal arrays land on the LOH (Large Object Heap, the heap that holds objects over 85,000 bytes) and Gen2 collections, not shown in the trimmed table, kick in. Still, at 10,000 records the gap is 218 times. At this size 33 milliseconds may look "good enough"; but when orders and customers reach 100,000, the naive version takes seconds and the dictionary version a few milliseconds.

In Production

The easiest place to catch complexity in code review is collection calls inside a loop. Contains, IndexOf, First, Any, Where(...).Count(), Remove and Insert(0, ...) are O(n) on a List<T>; inside a loop they produce O(n·m). If you see a lookup inside a loop, first ask "can this lookup become a HashSet or Dictionary before the loop?"

The same logic applies to the database and the network, only more expensively. Sending one query per element in a loop (the N+1 problem) means O(n) round trips, each of them milliseconds. The Include and projection solutions we saw in the Entity Framework Core (EF Core) series are the database equivalent of the dictionary refactor in this post.

Finally, if you make a refactor with a complexity claim, attach the measurement. Putting a benchmark table taken at two sizes, like the one above, next to the sentence "I brought it down from O(n·m) to O(n+m)" both proves your claim and makes it harder for someone to revert the change later.

Common Pitfalls

LINQ looking like a single line. orders.Where(o => customers.Any(c => c.Id == o.CustomerId)) is one line but two loops. What matters is not the number of lines but what's inside each call.

Calling a dependent inner loop O(n log n) or O(n). A triangular loop written with j < i is still Θ(n²).

Assuming every halving is log n. i /= 2 is log n; but if you copy half of the array with Array.Copy inside the loop, each step does O(n) work and the total is n + n/2 + n/4 + … = 2n, i.e. O(n). Count the number of steps and the cost of each step separately.

Enumerating an IEnumerable more than once. Rider's "possible multiple enumeration" warning and rule CA1851 in the .NET analyzers are not style warnings, they're hidden complexity warnings.

Relying on an implementation detail. OrderBy().First() is O(n) today, but that's an optimization, not a guarantee. Use the API (Application Programming Interface) that states your intent (MinBy, MaxBy).

A Small Experiment

★☆☆ Compute the number of steps of for (var i = 1; i < n; i *= 3) for n = 1,000 and n = 1,000,000 on paper first, then verify it with code.

★★☆ Write and solve the recurrence for this function: Process(int[] items, int length), which recursively processes half of an array and then walks the whole array once. Hint: T(n) = T(n/2) + n. Which case of the master theorem is it?

★★★ Measure OrderMatching.Naive for n = 10,000 orders with m = 100 customers and for n = 100 orders with m = 10,000 customers. Both predict n·m = 1,000,000 comparisons; why do the times differ? Also check whether, for m = 100, the dictionary's fixed cost is higher than the linear search.

In this post we only counted time. But the dictionary refactor wasn't free: we allocated an extra hash table for m customers. In the next post we move to the memory side: space complexity, the room recursion takes on the call stack, APIs that produce copies, and reading a 2 GB log file without loading it into memory.