Code review: what is the time complexity of this .NET code, and how would you make it faster? It loops over orders, calls products.FirstOrDefault(p => p.Id == line.ProductId) per line, builds a report with string +=, and checks seen.Contains(order.Id) on a List<int>.

1. A method for analysing any code

1. Name the inputs: O orders, L lines per order, P products, R output size.
2. Walk each loop and multiply by how many times it runs.
3. Expand every library call into its real cost (see the table below).
4. Add sequential parts, multiply nested parts.
5. Keep the dominant term for realistic sizes.

2. Hidden costs to expand

3. Why string += is quadratic

Strings are immutable, so each += allocates a new string and copies everything so far:

append 1: copy  1 chunk
append 2: copy  2 chunks
append 3: copy  3 chunks
...
append k: copy  k chunks
total   : 1 + 2 + ... + k = k(k+1)/2  -> O(k^2)

StringBuilder keeps a linked list of chunks and appends in amortised O(1), so the total is O(R). Once a string exceeds 85,000 bytes, every += also allocates on the Large Object Heap, which adds Gen 2 GC pressure.

4. Multiple enumeration of deferred LINQ

var active = orders.Where(o => o.IsActive);   // nothing runs yet
for (int i = 0; i < active.Count(); i++)      // Count() enumerates: O(n) each iteration
    Process(active.ElementAt(i));             // ElementAt(i): O(i) each

This is O(n²) from two different sources. Materialise once with ToList() and iterate that.

5. Making it linear: the two standard moves

Before: for each A, scan all of B            O(|A| * |B|)

         A ----> [ scan B linearly ]

After : build index over B once, then probe   O(|A| + |B|)

         B ----> Dictionary (one pass)
         A ----> Dictionary lookup O(1)

The second move is sorting both sides and merging (O(n log n)), which is what a database merge join does. Hash join versus nested-loop join in SQL execution plans is exactly the same trade-off.

6. Verifying with a profiler

• dotnet-counters monitor -n MyApp System.Runtime shows allocation rate and GC counts climbing with string +=.
• dotnet-trace collect plus a flame graph shows wide bars under FirstOrDefault or Contains.
• BenchmarkDotNet with [Params(1_000, 10_000, 100_000)] shows whether time grows 10× or 100× per 10× input.

7. Try it yourself

// Benchmark: dotnet add package BenchmarkDotNet; run with -c Release
[MemoryDiagnoser]
public class ReportBench
{
    [Params(1_000, 10_000)] public int N;
    private List<int> _ids = null!;

    [GlobalSetup] public void Setup() => _ids = Enumerable.Range(0, N).ToList();

    [Benchmark(Baseline = true)]
    public string Concat() { var s = ""; foreach (var i in _ids) s += i + ","; return s; }

    [Benchmark]
    public string Builder() { var sb = new StringBuilder(); foreach (var i in _ids) sb.Append(i).Append(','); return sb.ToString(); }
}

Compare the ratio between N = 1,000 and N = 10,000 for each method: about 100× for Concat, about 10× for Builder.

// BEFORE: O(O^2 + O*L*P + R^2)
var seen = new List<int>();
string report = "";
foreach (var order in orders)
{
    if (seen.Contains(order.Id)) continue;
    seen.Add(order.Id);
    foreach (var line in order.Lines)
    {
        var p = products.FirstOrDefault(p => p.Id == line.ProductId);
        report += $"{order.Id},{p?.Name},{line.Qty}\n";
    }
}

// AFTER: O(P + O*L + R)
var byId = products.ToDictionary(p => p.Id);
var seenIds = new HashSet<int>(orders.Count);
var sb = new StringBuilder();
foreach (var order in orders)
{
    if (!seenIds.Add(order.Id)) continue;
    foreach (var line in order.Lines)
    {
        byId.TryGetValue(line.ProductId, out var p);
        sb.Append(order.Id).Append(',').Append(p?.Name).Append(',').Append(line.Qty).Append('\n');
    }
}
var result = sb.ToString();

// Even better for big exports: stream rows instead of building one huge string
await using var writer = new StreamWriter(path);
foreach (var order in orders)
    foreach (var line in order.Lines)
        await writer.WriteLineAsync($"{order.Id},{byId.GetValueOrDefault(line.ProductId)?.Name},{line.Qty}");