Logarithms and Complexity

Logarithms and Complexity Growth

A logarithm is the mathematical inverse of exponentiation.

If:

then:

In other words, a logarithm asks: what exponent produces $n$?

Exponentiation:  2⁴ = 16       (2 multiplied by itself 4 times equals 16)
Logarithm:       log₂(16) = 4  (What power must 2 be raised to in order to get 16? Answer: 4)

In computer science, when the base $b$ of a logarithm is omitted in asymptotic notation, base $2$ ($\log_2 n$) is almost universally implied. This is because algorithmic operations frequently make binary decisions or divide data collections in half at each step.

$O(\log n)$ Growth

An $O(\log n)$ algorithm grows slowly as the input size increases. Its work increases by a small, constant amount (+1 step) even when $n$ becomes twice as large.

On a complexity-growth chart, $O(\log n)$ appears as a slowly rising curve that gradually flattens. It grows much more slowly than linear growth $O(n)$:

Logarithmic complexity is commonly related to searching, where each step can reduce the remaining search space substantially (typically by half).

Example: Binary Search

In a sorted array, Binary Search checks the middle element. If the target value is smaller than the middle element, the entire right half of the array is discarded. If the target is larger, the left half is discarded.

function binarySearch(sortedArr, target) {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (sortedArr[mid] === target) {
      return mid; // Target found
    }

    if (sortedArr[mid] < target) {
      left = mid + 1; // Discard left half
    } else {
      right = mid - 1; // Discard right half
    }
  }

  return -1; // Target not present
}

Notice how drastically $O(\log n)$ outperforms linear $O(n)$ as input size scales:

Doubling the dataset from $1$ million to $2$ million elements requires linear search to perform an extra $1{,}000{,}000$ operations, whereas binary search requires only $1$ additional comparison.

$O(n \log n)$ Growth

An $O(n \log n)$ algorithm (often called linearithmic) combines two factors:

• $n$: work that depends on the number of items (such as scanning or combining all $n$ elements at each level).
• $\log n$: a logarithmic number of stages, partitions, or tree levels.

On a complexity-growth chart, $O(n \log n)$ grows faster than $O(\log n)$ because it includes work for all $n$ items. However, the logarithmic factor still makes it much closer to linear growth than to quadratic growth ($O(n^2)$):

This complexity is commonly associated with efficient sorting algorithms, such as Merge Sort, Quick Sort (average case), and Heap Sort.

Example: Merge Sort

Merge Sort splits an array in half repeatedly until sub-arrays of size $1$ are reached (taking $\log n$ division levels). It then merges those sub-arrays back together in sorted order, performing $O(n)$ total work across each level:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // Recursive division
  const right = mergeSort(arr.slice(mid));      // Recursive division

  return merge(left, right); // O(n) work across O(log n) levels
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

Comparing $O(\log n)$ and $O(n \log n)$

Logarithms in Recursion

Logarithms also appear in recursion when recursive steps repeatedly reduce a problem. The number of recursive levels can be logarithmic when the problem becomes substantially smaller at each level.

When a recursive algorithm cuts the problem size in half ($n \to n/2 \to n/4 \dots \to 1$), the resulting call tree has a depth of $\log_2 n$:

Level 0:                 [Size n]                     --> 1 node
                          /    \
Level 1:           [Size n/2]  [Size n/2]             --> 2 nodes
                    /    \        /    \
Level 2:       [n/4]    [n/4]  [n/4]    [n/4]         --> 4 nodes
                ...      ...    ...      ...
Level log₂(n): [ 1 ]    [ 1 ]  [ 1 ]    [ 1 ]         --> n leaves

The overall time complexity depends on how much work occurs at each level:

1. Single-Branch Reduction $\to O(\log n)$ Time: If the algorithm only visits one child at each level (like recursive binary search), total operations equal the depth of the tree: $\text{Total Work} = O(1) \times \log_2 n = O(\log n)$

2. Full Divide-and-Conquer $\to O(n \log n)$ Time: If the algorithm visits both halves and does linear work combining them (like merge sort), the work at every level sums to $n$: $\text{Total Work} = n \text{ per level} \times \log_2 n \text{ levels} = O(n \log n)$

This connects logarithms directly to three core algorithmic patterns:

• Searching through a reduced space: Discarding large subsets of candidates with each comparison ($O(\log n)$).
• Sorting with logarithmic stages: Recombining divided sub-arrays over $\log n$ hierarchy levels ($O(n \log n)$).
• Recursive processes that reduce a problem repeatedly: Tree depth grows logarithmically when subproblems shrink by a constant factor ($\log_b n$).

Key Takeaways

• Inverse of Exponentiation: $\log_b(n) = x \iff b^x = n$. In CS, base $2$ ($\log_2 n$) is standard because problems are continually halved.
• $O(\log n)$ Efficiency: Logarithmic growth increases by only $1$ step when input doubles; commonly seen in search algorithms like Binary Search.
• $O(n \log n)$ Combination: Linearithmic algorithms do $n$ work across $\log n$ levels; standard for efficient sorting algorithms like Merge Sort.
• Recursion Tree Height: Repeatedly dividing a problem by a constant factor produces a recursion tree of height $O(\log n)$.