ON Linear Time

TL;DR

O(n) linear time means runtime grows in step with the input — doubling the data doubles the work. It's the floor for any algorithm that must look at every element (sums, filters, max/min, table scans), so the senior-engineer move is to make sure you only do it once, fuse passes, exit early when you can, and reach for a hash index when "every element" is actually a lookup in disguise.

How it works

O(n) — Linear Time

"Operation time grows proportionally with input size—doubling input doubles execution time."

❌ Bad example:

public class TradeAnalyzer
{
    public decimal CalculateAveragePrice(List<Trade> trades)
    {
        decimal sum = 0;
        foreach (var trade in trades)
        {
            sum += trade.Price; // O(n)
        }

        decimal count = 0;
        foreach (var trade in trades)
        {
            count++; // O(n) - unnecessary second pass
        }

        return sum / count;
    }
}

Two separate O(n) passes when one would suffice—wasted cycles.

✅ Good example:

public class TradeAnalyzer
{
    public decimal CalculateAveragePrice(List<Trade> trades)
    {
        if (trades.Count == 0) return 0;

        decimal sum = 0;
        foreach (var trade in trades)
        {
            sum += trade.Price;
        }

        // O(1) - Count property is cached
        return sum / trades.Count;
    }

    // Alternative LINQ (still O(n), more readable)
    public decimal CalculateAveragePriceLINQ(List<Trade> trades)
    {
        return trades.Any() ? trades.Average(t => t.Price) : 0;
    }
}

👉 Single pass through data, use cached Count for O(1) access.

🔥 Filtering with Where:

public class OrderFilter
{
    public IEnumerable<Order> GetLargeOrders(IEnumerable<Order> orders, decimal threshold)
    {
        // O(n) - single pass when enumerated
        return orders.Where(o => o.Amount > threshold);
    }

    public List<Order> GetLargeOrdersMaterialized(List<Order> orders, decimal threshold)
    {
        var result = new List<Order>();
        foreach (var order in orders)
        {
            if (order.Amount > threshold)
                result.Add(order); // O(1) amortized per Add
        }
        return result; // Total: O(n)
    }
}

👉 LINQ Where() is O(n) during enumeration—iterates once through all items.

🔥 Finding maximum:

public class PriceTracker
{
    public decimal FindMaxPrice(decimal[] prices)
    {
        if (prices.Length == 0) throw new ArgumentException("Empty array");

        decimal max = prices[0];
        for (int i = 1; i < prices.Length; i++)
        {
            if (prices[i] > max)
                max = prices[i];
        }
        return max; // O(n) - must check every element
    }

    // LINQ alternative (same complexity)
    public decimal FindMaxPriceLINQ(decimal[] prices)
    {
        return prices.Max(); // O(n)
    }
}

👉 Finding min/max in unsorted data requires checking every element.

🔥 String operations:

public class SymbolValidator
{
    public bool IsValidSymbol(string symbol)
    {
        // O(n) - where n is symbol.Length
        return symbol.All(c => char.IsLetterOrDigit(c));
    }

    public string FormatSymbol(string symbol)
    {
        // O(n) - creates new string with all chars uppercase
        return symbol.ToUpper();
    }
}

👉 String operations typically iterate through all characters: O(n).

💡 In trading systems:

• Summing positions, calculating totals, or aggregating trades is O(n).
• Filtering orders by criteria (price, symbol, time) requires scanning all.
• Accept O(n) when necessary, but avoid repeated scans—combine operations.

Quick recall Q&A