Binary Search (Recurrence Relation)

Aug 16, 2025

Updated 1 day ago

2 min read

Binary Search: Recurrence Relation Explained

Binary search is a fundamental search algorithm and data structure operation that finds a target value in a sorted array by repeatedly halving the search space. Its efficiency comes directly from this halving — and to formally prove that efficiency, we use a recurrence relation.

This note covers the mathematical derivation of binary search's time complexity from its recurrence, then explains recurrence relations as a concept in algorithm design more broadly.

Helper Functions

Floor Function

floor(x) — If $x$ is a real number, then $⌊ x ⌋$ is the greatest integer less than or equal to $x$ .

Example: $⌊ 3.7 ⌋ = 3$ , $⌊ 5 ⌋ = 5$

Ceil Function

ceil(x) — If $x$ is a real number, then $⌈ x ⌉$ is the smallest integer greater than or equal to $x$ .

Example: $⌈ 3.2 ⌉ = 4$ , $⌈ 5 ⌉ = 5$

Binary Search Recurrence Relation

Binary search works by:

Finding the middle element: $mi d = ⌊ \frac{l o w + hi g h}{2} ⌋$
Comparing the key with arr[mid]:
- If key == arr[mid] → element found
- If key < arr[mid] → search in left half
- If key > arr[mid] → search in right half

This gives the recursive equation:

T (n) = C_{1} + C_{2} + T! (\frac{n}{2})

Where:

$C_{1}$ = time to find the mid element
$C_{2}$ = time to compare key with mid
$T! (\frac{n}{2})$ = time to search the remaining half

Combining constants:

T (n) = C + T! (\frac{n}{2}), T (1) = O (1)

Solving the Recurrence by Expansion

Expanding level by level (the problem size halves at each level):

Lvl (0) T (n) = T (n /2) + 1

Lvl (1) T (n) = T (n / 2^{2}) + 1 + 1

Lvl (2) T (n) = T (n / 2^{3}) + 1 + 1 + 1

Lvl (3) T (n) = T (n / 2^{4}) + 1 + 1 + 1 + 1

⋮

Lvl (k) T (n) = T (n / 2^{k}) + k

The recursion bottoms out when $n / 2^{k} = 1, i . e . k = lo g_{2} n$ . Substituting:

T (n) = T! (\frac{n}{2 ^{k}}) + k = T (1) + lo g_{2} n = 1 + lo g_{2} n

T (n) = O (lo g_{2} n)

This is why binary search is so efficient — it only takes $lo g_{2} n$ comparisons to find any element in a sorted array of size $n$ . Compare this to quick sort or merge sort, which operate at $O (n lo g n)$ .

What is a Recurrence Relation?

A recurrence relation defines each term of a sequence as a function of its previous terms. Formally, given a sequence $a_{n} n = 0^{\infty}$ , a recurrence relation expresses $a_{n}$ in terms of $a n - 1, a_{n - 2}, \dots$

Fibonacci — The Classic Example

f (0) = 0, f (1) = 1

f (n) = f (n - 1) + f (n - 2) for n \geq 2

Each term is the sum of the two preceding terms. This is a classic linear recurrence relation.

General Form of a Linear Recurrence Relation

Given a sequence $a_{n}_{n = 0}^{\infty}$ , a linear recurrence relation with constant coefficients has the form:

a_{n} + c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} = f (n), n \geq k

Where:

$c_{1}, c_{2}, \dots, c_{k}$ are constants
$f (n)$ is some function of $n$
$k$ is the degree (order) of the recurrence

Types of Recurrence Relations

Homogeneous

When $f (n) = 0$ — the right-hand side is zero:

a_{n} + c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} = 0, n \geq k

Inhomogeneous

When $f (n) \neq = 0$ — there is a non-zero driving function on the right-hand side:

a_{n} + c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} = f (n), n \geq k

Examples

Relation	Type
$a_{n} - 4 a_{n - 1} = 0$	Homogeneous
$a_{n} - 3 a_{n - 1} + 6 a_{n - 2} = 4^{n}$	Inhomogeneous
$a_{n} + 2 a_{n - 2} = 5^{n}$	Inhomogeneous

Complexity Summary

Case	Time Complexity
Best (element at mid)	$O (1)$
Worst / Average	$O (lo g_{2} n)$

Binary search's $O (lo g n)$ complexity — proven through its recurrence — makes it one of the most efficient algorithms for searching in sorted data structures. For more on asymptotic analysis, see Asymptotic Notation.