ON2 Quadratic Time

TL;DR

O(n²) quadratic time grows with the square of the input — double the data and the work quadruples. It's the signature of nested loops over the same collection, Contains against a List<T> inside a loop, and naive string concatenation, and it's the complexity class that quietly destroys throughput as data scales; almost every O(n²) hotspot can be rewritten to O(n) by indexing one side with a HashSet or Dictionary.

How it works

O(n²) — Quadratic Time

"Operation time grows with the square of input size—doubling input quadruples execution time. Avoid in production."

❌ Bad example:

public class DuplicateDetector
{
    public List<Trade> FindDuplicateTrades(List<Trade> trades)
    {
        // O(n²) - nested loop comparing every pair
        var duplicates = new List<Trade>();

        for (int i = 0; i < trades.Count; i++)
        {
            for (int j = i + 1; j < trades.Count; j++)
            {
                if (trades[i].Id == trades[j].Id)
                {
                    duplicates.Add(trades[j]);
                }
            }
        }

        return duplicates;
    }
}

// 10,000 trades = 50 million comparisons
// 100,000 trades = 5 billion comparisons (system grinds to halt)

Nested loops over same dataset—classic O(n²) antipattern.

✅ Good example:

public class DuplicateDetector
{
    public List<Trade> FindDuplicateTrades(List<Trade> trades)
    {
        // O(n) - single pass with hash set
        var seen = new HashSet<int>();
        var duplicates = new List<Trade>();

        foreach (var trade in trades)
        {
            if (!seen.Add(trade.Id)) // Add returns false if already exists
            {
                duplicates.Add(trade);
            }
        }

        return duplicates;
    }

    // Alternative: find all duplicate groups
    public Dictionary<int, List<Trade>> GroupDuplicates(List<Trade> trades)
    {
        // O(n) - group by ID
        return trades
            .GroupBy(t => t.Id)
            .Where(g => g.Count() > 1)
            .ToDictionary(g => g.Key, g => g.ToList());
    }
}

// 100,000 trades = 100,000 operations (hash lookups)

👉 HashSet eliminates nested loop—O(1) lookups reduce O(n²) to O(n).

🔥 Cartesian product (intentional O(n²)):

public class PairGenerator
{
    public List<(Order Buy, Order Sell)> GenerateAllPairs(List<Order> buyOrders, List<Order> sellOrders)
    {
        // O(n * m) - intentionally generating all combinations
        var pairs = new List<(Order, Order)>();

        foreach (var buy in buyOrders)
        {
            foreach (var sell in sellOrders)
            {
                if (buy.Symbol == sell.Symbol)
                {
                    pairs.Add((buy, sell));
                }
            }
        }

        return pairs;
    }
}

👉 Sometimes O(n²) is necessary (all pairs, matrix operations), but minimize data size.

🔥 String concatenation in loops:

// ❌ O(n²) - avoid
public string BuildReport(List<Trade> trades)
{
    string report = "";
    foreach (var trade in trades)
    {
        report += $"{trade.Symbol},{trade.Price}\n"; // creates new string each iteration
    }
    return report;
}

// ✅ O(n) - use StringBuilder
public string BuildReportOptimized(List<Trade> trades)
{
    var sb = new StringBuilder();
    foreach (var trade in trades)
    {
        sb.AppendLine($"{trade.Symbol},{trade.Price}"); // modifies buffer in-place
    }
    return sb.ToString();
}

👉 String immutability makes concatenation O(n²)—use StringBuilder.

🔥 Avoiding nested loops:

// ❌ O(n²) - finding matching orders
public List<(Order, Order)> MatchOrders(List<Order> buyOrders, List<Order> sellOrders)
{
    var matches = new List<(Order, Order)>();
    foreach (var buy in buyOrders)
    {
        foreach (var sell in sellOrders) // nested loop
        {
            if (buy.Symbol == sell.Symbol && buy.Price >= sell.Price)
            {
                matches.Add((buy, sell));
            }
        }
    }
    return matches;
}

// ✅ O(n + m) - index by symbol first
public List<(Order, Order)> MatchOrdersOptimized(List<Order> buyOrders, List<Order> sellOrders)
{
    // O(n) - group sell orders by symbol
    var sellsBySymbol = sellOrders
        .GroupBy(o => o.Symbol)
        .ToDictionary(g => g.Key, g => g.ToList());

    var matches = new List<(Order, Order)>();

    // O(n) - iterate buy orders and lookup matching sells
    foreach (var buy in buyOrders)
    {
        if (sellsBySymbol.TryGetValue(buy.Symbol, out var sells))
        {
            foreach (var sell in sells.Where(s => buy.Price >= s.Price))
            {
                matches.Add((buy, sell));
            }
        }
    }

    return matches;
}

👉 Index one collection to avoid scanning it repeatedly—reduces O(n * m) to O(n + m).

💡 In trading systems:

• Never use O(n²) for matching engines, order lookups, or real-time processing.
• Profile nested loops—if data grows, O(n²) becomes bottleneck.
• Use dictionaries, hash sets, or sorting to eliminate inner loops.

Quick recall Q&A