OLogN Logarithmic Time

TL;DR

O(log n) logarithmic time means each step throws away a constant fraction of the remaining work — doubling the data only adds one more step. This is the regime of binary search, balanced trees (SortedSet, SortedDictionary) and B-tree database indexes, which is why a billion-row indexed lookup finishes in roughly thirty comparisons instead of a billion.

How it works

O(log n) — Logarithmic Time

"Operation time grows logarithmically—doubling input size adds only one more step."

❌ Bad example:

public class PriceLookup
{
    private List<PriceLevel> _prices = new(); // unsorted

    public decimal FindPriceNearTarget(decimal target)
    {
        // O(n) - must check every price
        return _prices
            .Select(p => p.Price)
            .OrderBy(p => Math.Abs(p - target))
            .First();
    }
}

// Searching 1 million prices requires checking all
var price = lookup.FindPriceNearTarget(150.00m);

Linear search doesn't exploit any structure—wasteful for large datasets.

✅ Good example:

public class PriceLookup
{
    private List<PriceLevel> _prices = new(); // sorted

    public decimal FindPriceNearTarget(decimal target)
    {
        // O(log n) - binary search
        int index = _prices.BinarySearch(new PriceLevel { Price = target });
        if (index < 0) index = ~index; // insertion point

        // Check nearby prices
        return _prices[Math.Max(0, index - 1)].Price;
    }

    public void AddPrice(PriceLevel price)
    {
        int index = _prices.BinarySearch(price);
        if (index < 0) index = ~index;
        _prices.Insert(index, price); // O(n) insert, but search is O(log n)
    }
}

// Searching 1 million sorted prices takes ~20 comparisons
var price = lookup.FindPriceNearTarget(150.00m);

👉 Binary search halves the search space each step: O(log₂ n).

🔥 SortedSet for automatic ordering:

public class OrderPriceIndex
{
    private SortedSet<decimal> _buyPrices = new();
    private SortedSet<decimal> _sellPrices = new();

    public void AddBuyOrder(decimal price)
    {
        // O(log n) - balanced tree insert
        _buyPrices.Add(price);
    }

    public decimal GetBestBid()
    {
        // O(log n) - find max in tree
        return _buyPrices.Max;
    }

    public IEnumerable<decimal> GetPricesInRange(decimal min, decimal max)
    {
        // O(log n + k) - where k is result count
        return _buyPrices.GetViewBetween(min, max);
    }
}

👉 SortedSet (red-black tree) maintains order with O(log n) operations.

🔥 Dictionary resizing:

public class TradeCache
{
    // Dictionary internal resizing is O(n), but happens O(log n) times
    // as capacity doubles: 4, 8, 16, 32, 64...
    private Dictionary<int, Trade> _trades = new();

    public void AddTrade(Trade trade)
    {
        // Amortized O(1), but understanding the log n resize pattern is key
        _trades[trade.Id] = trade;
    }
}

👉 Doubling strategy means O(log n) resizes over n insertions.

💡 In trading systems:

• Use binary search for finding price levels in sorted order books.
• SortedSet for maintaining best bid/ask with efficient range queries.
• B-tree indexes in databases provide O(log n) lookups for billions of records.

Quick recall Q&A