Engineering Fluency OS

Why This Matters

Every time you hear "O(log n)" in algorithm analysis, you are hearing about logarithms. Binary search finds an element in a sorted array of one million items in just 20 steps because log base 2 of 1,000,000 is about 20. That is the power of logarithmic thinking: doubling the input only adds one more step.

Logarithms are the inverse of exponential growth. If 2 to the power of 10 is 1024, then log base 2 of 1024 is 10. Understanding this relationship is essential for analyzing algorithms, designing data structures like balanced trees, and reasoning about anything that halves or doubles repeatedly -- from binary search to network protocols to cryptocurrency mining.

Define Terms

Visual Model

Exponential 2^xDoubles each step

Logarithm log2(x)Inverse of 2^x

Linear xGrows steadily

Halving Pattern

Binary Search

O(log n)

Growth Comparisonexp >> linear >> log

The full process at a glance. Click Start tour to walk through each step.

Logarithms count halvings. This is why binary search on a million items takes only 20 steps.

Code Example

Code

// Logarithm basics
console.log("log2(8):", Math.log2(8));       // 3
console.log("log2(1024):", Math.log2(1024)); // 10
console.log("log2(1000000):", Math.log2(1000000).toFixed(1)); // 19.9

// Natural log (base e) and log base 10
console.log("ln(e):", Math.log(Math.E));     // 1
console.log("log10(1000):", Math.log10(1000)); // 3

// Change of base: logb(x) = ln(x) / ln(b)
function logBase(base, x) {
  return Math.log(x) / Math.log(base);
}
console.log("log3(27):", logBase(3, 27)); // 3

// Count halvings until reaching 1
function countHalvings(n) {
  let count = 0;
  while (n > 1) {
    n = Math.floor(n / 2);
    count++;
  }
  return count;
}
console.log("halvings(1000):", countHalvings(1000)); // 10
console.log("halvings(1000000):", countHalvings(1000000)); // 19

// Binary search: O(log n) in action
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1, steps = 0;
  while (lo <= hi) {
    steps++;
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) {
      console.log(`Found in ${steps} steps`);
      return mid;
    }
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

const sorted = Array.from({length: 1000000}, (_, i) => i);
binarySearch(sorted, 654321); // Found in ~20 steps

Interactive Experiment

Try these exercises:

Compute log2(1), log2(2), log2(4), log2(16), log2(256). What pattern do you see?
How many times can you halve 1 billion before reaching 1? Verify with code.
Run binary search on arrays of size 100, 10000, and 1000000. Count the steps. Are they close to log2 of each size?
What is log2(0)? What happens in code? Why does this make sense?
If a balanced binary tree has 1 million nodes, how many levels does it have?

Quick Quiz

Coding Challenge

Power of Two Checker

Write a function called `isPowerOfTwo` that returns true if a positive integer n is a power of 2, and false otherwise. Powers of 2 are: 1, 2, 4, 8, 16, 32, ... Hint: if n is a power of 2, then log2(n) is a whole number. Alternatively, use the bit trick: n & (n - 1) === 0 for powers of 2.

Loading editor...

Real-World Usage

Logarithms are deeply embedded in computer science:

Big O analysis: O(log n) algorithms like binary search and balanced trees are the gold standard for search operations.
Data structures: B-trees, red-black trees, and skip lists all achieve O(log n) operations through logarithmic depth.
Information theory: Information content is measured in bits, which are log2. A byte represents log2(256) = 8 bits of information.
Networking: The number of hops in a distributed hash table (like Chord) is O(log n) of the network size.
Database indexing: B+ tree indices give O(log n) lookups. This is why indexed queries on millions of rows are fast.

Logarithms