Binary Search (Recurrence Relation)

Created

Aug 16, 2025

Last Modified

3 months ago

Binary Search

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

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

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

Recursive Equation

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

$t (\frac{n}{2})$ id
$C_{2}$ = Time to comparing key with mid
$t\left(\frac{ $d$ 2}\right)$ = Time to search in the remaining half $n$ the array

$t (n) = C + t (\frac{n}{2})$ $k$ $t (1) = O (1)$

$Lv l (1) T (n) = T (n / 2^{2}) + 1 + 1$

$Lv l (2) T (n) = T (n / 2^{3}) + 1 + 1 + 1$

$Lv l (3) T (n) = T (n / 2^{4}) + 1 + 1 + 1 + 1$

$⋮$

$Lv l (k) T (n) = T (n / 2^{k}) + 1 \cdot k = T (n / 2^{3}) + 1 + 1 + 1$

$Lv l (3) T (n) = T (n / 2^{4}) + 1 + 1 + 1 + 1$

$⋮$

$Lv l (k) T (n) = T (n / 2^{k}) + 1 \cdot k$

T (n) = T (\frac{n}{2 ^{k}}) + k

T (n) = T (\frac{n}{n}) + lo g_{2} n

T (n) = 1 + l o g_{2} n

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

Def ${a_{n}}_{n = 0}^{\infty}$ a mapping from natural num $n + 1^{t h}$ me set.
A recurrence relation defines each term of t $f (n)$ uence as a function of its $c_{1}, c_{2}, \dots, c_{k}$ ibonacci Relation

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

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

This is a classic recurrence relation.

Let ${a_{n}}_{n = 0}^{\infty}$ Is a sequence where an is $n + 1^{t h}$ term of the sequence then a relation of type

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

$f (n)$ is some functi $a_{n} - 4 a_{n - 1} = 0$ , \dots, c_k$ are con $a_{n} - 3 a_{n - 1} + 6 a_{n - 2} = 4^{n}$ er, called the degree of $a_{n} - a_{n - 1}^{2} + 2 a_{n - 2} = 5^{n}$ inear recurrance relation with constant coefficient.

condition

Homogeneous Linear Recurrence Relation with constant coefficient
$a_{n} + C_{1} a_{n - 1} + C_{2} a_{n - 2} + \dots + C_{k} a_{n - k} = 0 n \geq k$
Inhomogeneous Linear Recurrence Relation with constant coefficient
$f (n) = a_{n} + C_{1} a_{n - 1} + C_{2} a_{n - 2} + \dots + C_{k} a_{n - k} \neq = 0$