A .NET API endpoint was fast in testing but gets slower every month as production data grows, and now times out for your biggest customers. How would you find and fix an algorithmic complexity problem, and stop it happening again?

1. Measuring growth empirically

Run the operation at n, 2n, 4n and look at the ratio of times:

The log-log slope of time versus n gives the exponent directly. This works on production metrics too: plot log(latency) against log(rows per tenant).

2. Reading a flame graph

|------------------------------ GetStatement (100%) -------------------------------|
|---------- BuildLines (85%) ----------------------------|-- Serialise (10%) --|
|-- Enumerable.Where/FirstOrDefault (70%) --|-- Concat --|

Width is time. A library method like FirstOrDefault taking 70% of a request is the signature of a lookup inside a loop. Look at its caller, not at LINQ itself.

3. The I/O version of O(n²): N+1

SELECT * FROM Accounts WHERE TenantId = @t          -- 1 query
SELECT * FROM Transactions WHERE AccountId = @a1    -- n queries
SELECT * FROM Transactions WHERE AccountId = @a2
...

Each round trip costs about 0.5–2 ms even if the query is instant, so 2,000 accounts is several seconds of pure latency. Fixes in EF Core: Include (consider AsSplitQuery for multiple collections), projections with Select, or one query for all child rows then ToLookup in memory.

4. In-memory join patterns

// O(a * t): scan transactions per account
foreach (var a in accounts)
    a.Lines = transactions.Where(t => t.AccountId == a.Id).ToList();

// O(a + t): group once
var byAccount = transactions.ToLookup(t => t.AccountId);
foreach (var a in accounts)
    a.Lines = byAccount[a.Id].ToList();   // ILookup returns empty for missing keys

This is exactly the hash join a database would choose.

5. Guarding with tests

[Fact]
public void Statement_scales_linearly()
{
    var t1 = Time(() => Build(Generate(20_000)));
    var t2 = Time(() => Build(Generate(80_000)));
    // 4x data should be roughly 4x time; allow noise but catch quadratic (16x)
    Assert.True(t2 < t1 * 8, $"Grew {t2 / t1:F1}x for 4x data");
}

Ratio tests are less flaky than absolute thresholds because they cancel out machine speed. Run them in a dedicated performance stage, not on every unit test run.

6. Defence in depth

 request -> [limits: page size, max items]
         -> [algorithm: indexes, batching, streaming]
         -> [database: indexes, query plans]
         -> [observability: latency by tenant size, SQL count per request]
         -> [CI: perf test at production n]

Also log n with each request (row counts, item counts). Without it you cannot correlate latency with data size.

7. Try it yourself

Take any endpoint in your app that loops over a collection. Generate 1×, 4× and 16× the data, time it, and compute the ratios. Then run dotnet-trace collect --profile cpu-sampling during the 16× run and open the trace in Speedscope (dotnet-trace convert --format Speedscope). Find the widest frame you did not expect.

// BEFORE: O(accounts * transactions) CPU plus N+1 queries for categories
public async Task<Statement> GetStatementBefore(int tenantId)
{
    var accounts = await db.Accounts.Where(a => a.TenantId == tenantId).ToListAsync();
    var transactions = await db.Transactions.Where(t => t.TenantId == tenantId).ToListAsync();
    var lines = new List<Line>();
    foreach (var a in accounts)
        foreach (var t in transactions.Where(t => t.AccountId == a.Id))     // scan per account
            lines.Add(new Line(a.Name, t.Amount, t.Category.Name));          // lazy load per row
    return new Statement(lines);
}

// AFTER: one query with projection, grouped once, O(a + t)
public async Task<Statement> GetStatementAfter(int tenantId, CancellationToken ct)
{
    var accounts = await db.Accounts
        .Where(a => a.TenantId == tenantId)
        .Select(a => new { a.Id, a.Name })
        .ToListAsync(ct);

    var byAccount = (await db.Transactions
        .Where(t => t.TenantId == tenantId)
        .Select(t => new { t.AccountId, t.Amount, Category = t.Category.Name })   // join in SQL
        .ToListAsync(ct))
        .ToLookup(t => t.AccountId);

    var lines = new List<Line>();
    foreach (var a in accounts)
        foreach (var t in byAccount[a.Id])
            lines.Add(new Line(a.Name, t.Amount, t.Category));
    return new Statement(lines);
}

// Log n so latency can be correlated with data size
logger.LogInformation("Statement built for {TenantId}: {Accounts} accounts, {Lines} lines in {ElapsedMs} ms",
    tenantId, accounts.Count, lines.Count, sw.ElapsedMilliseconds);