Logarithmic time complexity describes running time that grows with the logarithm of an input size or another stated parameter. For a balanced tree with n elements, a height of log(n) makes operations proportional to that height rather than to every element. section 2.9.1 section 9.3.3
Use logarithmic bounds to evaluate structures and operations under explicit assumptions:
- A binary heap guarantees logarithmic worst-case running time for its common operations, with comparisons proportional to log₂(N). section 2.9.1
- A D-way heap performs insertion in at most logD(n) swaps while restoring heap order. section 2.6.3
- A dynamic array can make an otherwise logarithmic insertion bound amortized rather than worst-case because resizing occurs periodically. section 2.6.3
- A balanced k-d tree supports worst-case logarithmic insertion and search when constructed from a known point set and left mostly unchanged. section 9.3.3
Priority queues and heaps
A task manager that consumes tasks one at a time does not need a totally sorted list. A priority queue preserves partial ordering, allowing common operations to require logarithmic time. In a ternary max-heap, inserting a task with priority 9.5 appends it and bubbles it upward until the heap properties are restored. section 2.3.1 section 2.6.3
O(log2(N)) = O(log3(N)) = O(log(N))
Compare logarithms with different bases through asymptotic notation: changing the base alters only a constant factor. section 2.9.1
