O1 Constant Time

TL;DR

O(1) constant time means the work an operation does never grows with the size of the input — a million-entry dictionary lookup costs the same as a ten-entry one. Reaching it usually means choosing the right structure (hash tables, arrays, head/tail-pointer queues) and trading some memory for predictably fast reads, which is what keeps hot paths like order lookups deterministic under load.

How it works

O(1) — Constant Time

"Operation time is independent of input size—always takes the same number of steps."

❌ Bad example:

public class OrderBook
{
    private List<Order> _orders = new();

    public Order FindOrderById(int orderId)
    {
        // O(n) - must scan entire list
        return _orders.FirstOrDefault(o => o.Id == orderId);
    }
}

// Finding order in 1 million orders requires scanning all
var order = orderBook.FindOrderById(12345); // slow!

Linear search scales poorly—doubling orders doubles search time.

✅ Good example:

public class OrderBook
{
    private Dictionary<int, Order> _orders = new();

    public Order FindOrderById(int orderId)
    {
        // O(1) - hash table lookup
        _orders.TryGetValue(orderId, out var order);
        return order;
    }

    public void AddOrder(Order order)
    {
        // O(1) - hash table insert
        _orders[order.Id] = order;
    }
}

// Finding order in 1 million orders is instant
var order = orderBook.FindOrderById(12345); // fast!

👉 Dictionary uses hashing for O(1) lookups regardless of size.

🔥 Array indexing:

public class PriceHistory
{
    private decimal[] _prices = new decimal[1000];

    public decimal GetPriceAt(int index)
    {
        // O(1) - direct memory access
        return _prices[index];
    }

    public void SetPriceAt(int index, decimal price)
    {
        // O(1) - direct memory write
        _prices[index] = price;
    }
}

👉 Array indexing is O(1)—memory address is calculated directly.

🔥 Stack/Queue operations:

public class TradeQueue
{
    private Queue<Trade> _pendingTrades = new();

    public void EnqueueTrade(Trade trade)
    {
        // O(1) - add to end
        _pendingTrades.Enqueue(trade);
    }

    public Trade ProcessNextTrade()
    {
        // O(1) - remove from front
        return _pendingTrades.Dequeue();
    }
}

👉 Queue operations are O(1) because they maintain head/tail pointers.

💡 In trading systems:

• Use Dictionary for order lookups by ID—critical for cancel/modify operations.
• Cache latest prices in arrays or dictionaries for O(1) access.
• Use HashSet for duplicate detection during order validation.

Quick recall Q&A