Logarithms in Algorithms

Learning Objectives

By the end of this section, you will be able to:

1. Understand what logarithms are and why they're fundamental to algorithm analysis
2. Recognize logarithmic patterns in algorithms like binary search and divide-and-conquer
3. Calculate and manipulate logarithms using key properties
4. Explain why the logarithm base doesn't matter in Big-O notation
5. Connect logarithms to real-world systems like databases, search engines, and tree structures
6. Appreciate the dramatic efficiency that logarithmic algorithms provide at scale

Why This Matters: Logarithms are the mathematical foundation of efficient algorithms. They explain why binary search can find an item among a billion in just 30 steps, why balanced trees remain fast as they grow, and why divide-and-conquer algorithms are so powerful. Understanding logarithms transforms algorithm analysis from memorization to intuition.

The Story Behind Logarithms

Long before computers existed, mathematicians faced a practical problem: multiplication and division of large numbers were incredibly tedious and error-prone. In the early 17th century, Scottish mathematician John Napier invented a revolutionary tool—the logarithm.

The Original Purpose

Napier's insight was brilliant: multiplication can be converted to addition using logarithms. If you need to multiply two large numbers, say 3,456 × 7,891:

1. Look up log(3,456) ≈ 3.539 and log(7,891) ≈ 3.897 in a table
2. Add them: 3.539 + 3.897 = 7.436
3. Look up the antilog: 10^7.436 ≈ 27,279,696

This technique powered centuries of scientific calculation and navigation before calculators. Slide rules—mechanical logarithm computers—helped send astronauts to the moon!

Logarithms in Computer Science

In computer science, logarithms gained a new and profound importance: they describe how many times you can divide a problem in half before reaching a single element. This is the essence of efficient algorithms.

Definition: What is a Logarithm?

A logarithm answers a fundamental question: "What power do I need to raise a base to, in order to get a given number?"

Formal Definition

The logarithm base $b$ of $x$, written $\log_b(x)$, is the exponent $y$ such that:

In other words, $\log_b(x)$ asks: "To what power must I raise $b$ to get $x$?"

Examples with Different Bases

Intuitive Understanding

Think of logarithms as counting multiplications:

• log₂(n): How many times must I multiply 2 by itself to reach n?
• Equivalently: How many times can I divide n by 2 before reaching 1?

For example, $\log_2(1024) = 10$ because:

11024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1
2  1     2     3     4     5    6    7   8   9  10 divisions

Interactive: Logarithm Explorer

Use this interactive tool to explore logarithms with different bases. Notice how all logarithm curves have the same fundamental shape—they differ only by a constant factor.

Key Logarithm Properties

These properties are essential for analyzing algorithms and simplifying expressions. Each property corresponds to a rule about exponents.

The Three Fundamental Properties

Additional Important Properties

Change of Base Formula

The change of base formula is particularly important in computer science:

This means any logarithm can be converted to any other base by dividing by a constant. This constant factor is why the base doesn't matter in Big-O notation.

math.log2(8) = 3.0

log₁₀(1024) / log₁₀(2) = 3.01 / 0.301 = 10.0

1# Computing logarithms in Python
2import math
3
4n = 1024
5
6# Different bases, same pattern
7log_base_2 = math.log2(n)        # 10.0
8log_base_10 = math.log10(n)      # 3.010...
9log_natural = math.log(n)        # 6.931...
10
11# Converting between bases
12log_2_from_10 = math.log10(n) / math.log10(2)  # 10.0
13log_2_from_e = math.log(n) / math.log(2)       # 10.0
14
15# Verify the relationship
16ratio = log_base_2 / log_base_10  # ≈ 3.322
17# This is always log₂(10) ≈ 3.322

Why Logarithms Appear in Algorithms

Logarithms appear in algorithms for a fundamental reason: they describe repeated halving (or more generally, repeated division). This pattern emerges in three main scenarios:

1. Searching in Sorted Data

When searching a sorted collection, you can eliminate half the remaining elements with each comparison. Starting with $n$ elements:

The number of steps to reach 1 element is $\log_2(n)$.

2. Balanced Tree Heights

In a balanced binary tree with $n$ nodes, each level doubles the number of nodes. A tree of height $h$ can hold $2^h - 1$ nodes. Inverting this:

3. Divide and Conquer Recursion

When a problem of size $n$ is divided into smaller subproblems (typically of size $n/2$), the recursion depth is $\log(n)$. This is why algorithms like merge sort and quicksort have $O(n \log n)$ complexity.

Case Study: Binary Search

Binary search is the canonical example of logarithmic complexity. It searches a sorted array by repeatedly dividing the search space in half.

The Algorithm

If arr = [1,3,5,7,9], mid=2 (value 5), target=7: search [7,9]

1def binary_search(arr, target):
2    """
3    Search for target in sorted array arr.
4    Returns index if found, -1 otherwise.
5    Time Complexity: O(log n)
6    """
7    left, right = 0, len(arr) - 1
8
9    while left <= right:
10        mid = (left + right) // 2
11
12        if arr[mid] == target:
13            return mid           # Found!
14        elif arr[mid] < target:
15            left = mid + 1       # Search right half
16        else:
17            right = mid - 1      # Search left half
18
19    return -1  # Not found

Why O(log n)?

Each iteration eliminates half the remaining elements. After $k$ iterations, we have:

We're done when only 1 element remains, so we solve for $k$:

Interactive: Binary Search in Action

Watch how binary search eliminates half the search space at each step. Notice how even with 64 elements, it takes at most 6 comparisons.

Case Study: Tree Heights

The height of a balanced tree is logarithmic in the number of nodes. This is why tree-based data structures (BSTs, heaps, B-trees) provide efficient operations.

The Relationship

For a balanced binary tree with $n$ nodes:

• Level 0 (root): 1 node = 2⁰
• Level 1: 2 nodes = 2¹
• Level 2: 4 nodes = 2²
• Level k: 2^k nodes

A complete binary tree of height $h$ has $2^{h+1} - 1$ nodes. Solving for height:

Interactive: Tree Height Visualization

Why This Matters

Tree operations (search, insert, delete) traverse from root to leaf. In a balanced tree:

• 1,000 nodes: height ≈ 10, so operations take ~10 steps
• 1,000,000 nodes: height ≈ 20, so operations take ~20 steps
• 1,000,000,000 nodes: height ≈ 30, so operations take ~30 steps

A billion-node tree is only 50% taller than a million-node tree!

Case Study: Divide and Conquer

Divide and conquer algorithms split problems into smaller subproblems, solve them recursively, and combine the results. The recursion depth is logarithmic because each level reduces problem size by a constant factor.

The Pattern

A typical divide-and-conquer recurrence looks like:

Where:

• $a$ = number of subproblems
• $n/b$ = size of each subproblem
• $f(n)$ = work to divide and combine

The recursion depth is $\log_b(n)$ because we divide by $b$ at each level.

Interactive: Divide and Conquer Decomposition

Merge Sort Example

Merge sort divides an array in half ($b = 2$), makes 2 recursive calls ($a = 2$), and does $O(n)$ work to merge:

There are $\log_2(n)$ levels, each doing $O(n)$ work total:

1def merge_sort(arr):
2    """
3    Sort array using merge sort.
4    Time Complexity: O(n log n)
5    """
6    if len(arr) <= 1:
7        return arr              # Base case
8
9    mid = len(arr) // 2
10    left = merge_sort(arr[:mid])   # Recursive call (n/2)
11    right = merge_sort(arr[mid:])  # Recursive call (n/2)
12
13    return merge(left, right)      # O(n) work
14
15def merge(left, right):
16    """Merge two sorted arrays into one sorted array."""
17    result = []
18    i = j = 0
19
20    while i < len(left) and j < len(right):
21        if left[i] <= right[j]:
22            result.append(left[i])
23            i += 1
24        else:
25            result.append(right[j])
26            j += 1
27
28    result.extend(left[i:])
29    result.extend(right[j:])
30    return result

Common Logarithmic Complexities

Here are the most common complexity classes involving logarithms:

The Log n Factor: What It Represents

The $\log n$ factor typically represents one of:

• Recursion depth: How many times you divide the problem (merge sort)
• Tree height: How many levels in a balanced tree structure (heap sort)
• Bits in the input: Number of binary digits needed to represent n (radix sort)

Why the Base Doesn't Matter in Big-O

You'll often see $O(\log n)$ written without specifying the base. This is intentional: in asymptotic analysis, the base is absorbed by the constant factor.

The Mathematical Reason

Using the change of base formula:

The factor $\frac{1}{\log_b(a)}$ is a constant that Big-O notation ignores. Therefore:

Concrete Example

The ratio log₂(n)/log₁₀(n) is always 3.32 (which equals log₂(10)). This constant multiplier is exactly what Big-O ignores.

Real-World Impact

The practical impact of logarithmic complexity is staggering. Let's examine some real-world scales:

Database Indexing

Modern databases use B-trees with branching factors around 100-1000. For a database with 10 billion records:

Just 5 disk accesses to find any record among 10 billion! Without indexing, you'd need to scan all 10 billion records.

Internet Search

Google indexes approximately 100 billion web pages. A tree-based index structure with branching factor 1000:

Four index lookups can narrow down from 100 billion pages to a manageable set!

Version Control (Git)

Git uses Merkle trees (hash trees) to efficiently compare repositories. Comparing two repositories with millions of files:

• Without tree structure: O(n) = millions of comparisons
• With Merkle tree: O(log n) ≈ 20 hash comparisons to find differences

Comparison: Linear vs Logarithmic at Scale

The Takeaway: Logarithmic algorithms don't just run faster—they transform impossible problems into trivial ones. A billion-element search in 30 steps is the difference between instant results and hours of waiting.

Summary

In this section, we've explored logarithms—one of the most important mathematical concepts in algorithm analysis:

Key Concepts

Key Formulas

What's Next

In the upcoming sections, we'll explore:

1. Summation Formulas and Series: Essential for analyzing loops and recursive algorithms
2. Proof Techniques: Mathematical induction and other methods for proving algorithm correctness
3. Probability Basics: Randomized algorithms and expected case analysis

Knowledge Check

Test your understanding of logarithms in algorithms with this quiz:

Exercises

Computation Exercises

1. Calculate: log₂(256), log₂(2048), log₃(243), log₁₀(1,000,000)
2. Simplify using logarithm properties: log₂(32 × 64), log₂(1024 / 32), log₂(8⁵)
3. Convert log₂(1000) to use base 10. Verify your answer with a calculator.
4. If log₂(n) = 20, what is n? If log₂(n) = 30?

Algorithm Analysis Exercises

1. A sorted array has 1,000,000 elements. What is the maximum number of comparisons binary search will make?
2. A balanced ternary tree (each node has 3 children) has 1,000,000 nodes. What is its height?
3. How many times can you halve the number 1,000,000,000 before reaching 1?
4. An algorithm has recurrence T(n) = 2T(n/2) + n. Write out the first 4 levels of the recursion tree for n = 64. What is the total work at each level?

Conceptual Questions

1. Why do we say O(log₂ n) = O(log₁₀ n) = O(log n), but we can't say O(n) = O(n²)?
2. A database can do binary search on an index in O(log n) time. Why might it use a B-tree with branching factor 100 instead of a binary tree?
3. If doubling the input size adds one more step to an algorithm, what is its complexity?
4. Explain intuitively why merge sort is O(n log n) while bubble sort is O(n²).

Programming Challenges

1. Implement a function that computes log₂(n) using only addition and subtraction (no built-in log functions). Count how many times you halve n.
2. Modify binary search to return the number of comparisons made. Test on arrays of size 100, 1000, 10000, and verify the results match log₂(n).
3. Write a function to compute the height of a complete binary tree given the number of nodes. Verify using log₂(n).

In the next section, we'll explore Summation Formulas and Series—essential tools for analyzing loops and computing total work in algorithms.