# O(log n) - Logarithmic Time

> Cuts the problem in half each step — searching a billion items in ~30 steps.

- **Category**: Big O
- **Subcategory**: complexity
- **Canonical URL**: https://designpattern.fyi/big_o/logarithmic-time/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
Git bisect — finding which commit introduced a bug in a repo of 1,024 commits takes only 10 binary search steps. Database B-tree index lookup — finding a row in a 100M row table takes ~27 B-tree node reads. Both are textbook O(log n).



## Implementation Example

```javascript
// O(log n) — Binary Search (iterative, avoids stack overhead)
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1; // Bitwise right shift — no overflow risk
    if (arr[mid] === target) return mid;
    arr[mid] < target ? lo = mid + 1 : hi = mid - 1;
    // Each iteration halves the search space — O(log n) total
  }
  return -1;
}

// O(log n) — Fast exponentiation (square instead of multiply n times)
function fastPow(base, exp) {
  if (exp === 0) return 1;
  if (exp % 2 === 0) {
    const half = fastPow(base, exp / 2); // Recurse on half — O(log n) depth
    return half * half;
  }
  return base * fastPow(base, exp - 1);
}

// Demo: binary search on 1 billion items takes ~30 iterations
// Math.ceil(Math.log2(1_000_000_000)) === 30

```



## Trade-offs


### Advantages

- Handles enormous datasets with minimal steps — 1B items in ~30 steps

- Standard in databases (B-tree indexes), language runtimes (TreeMap), and system libraries

- Far better than O(n) for large sorted datasets

- Stack depth for recursive divide-and-conquer is only O(log n) deep




### Considerations & Drawbacks

- Data usually needs to be sorted first — sorting is at least O(n log n)

- Tree structures need balancing to guarantee O(log n) — unbalanced trees degrade to O(n)

- More complex to implement than linear scan

- Overhead from pointer chasing in tree structures — worse cache locality than array scan for small n







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)