Notation for Divide and Conquer Algorithms

Here we collect notation related to the divide and conquer algorithms (and the problems they solve).

Merge Sort

Notation Meaning
$a_1,\dots,a_n$The $n$ numbers that need to be sorted
MergeSort$(a,n)$Run the merge sort algorithm on the $n$ numbers in the array $a$.
$a_L,a_R$$a_L=a_1,\dots,a_{\lfloor n/2\rfloor}$ and $a_R=a_{\lfloor n/2\rfloor+1},\dots,a_n$.

Integer Multiplication

Notation Meaning
$a=(a_{n-1},\dots,a_0)$ and $b=(b_{n-1},\dots,b_0)$Binary representation of numbers $a$ and $b$ (with e.g. $a_{n-1}$ being the MSB) so that we want to output $a\cdot b$.
$\text{Dec}(a)$Decimal representation of $a$, i.e. $\text{Dec}(a)=\sum_{i=0}^{n-1} a_i\cdot 2^i$.
$a^1, a^0$$a^1=(a_{n-1},\dots,a_{\lceil n/2\rceil})$ and $a^0=(a_{\lceil n/2\rceil-1},\dots, a_0)$. Note that $\text{Dec}(a) = \text{Dec}(a^1)\cdot 2^{\lceil n/2\rceil}+\text{Dec}(a^0)$.

Counting Inversions

Notation Meaning
$a_1,\dots,a_n$The input numbers (in an array $a$).
An inversion $(i,j)$A pair $(i,j)$ is an inversion in an array $a$ if (1) $i < j$ and (2) $a_i > a_j$.
$a_L,a_R$$a_L=a_1,\dots,a_{\lceil n/2\rceil}$ and $a_R=a_{\lceil n/2\rceil+1},\dots,a_n$.

Closest Pair of points

Notation Meaning
$p_i=(x_i,y_i)$A point (in two dimension).
$d(p_i,p_j)$Euclidean distance between $p_i$ and $p_j$, defined as $d(p_i,p_j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$.
$P=\{p_1,\dots,p_n\}$Set of $n$ two dimensional points.
$P_x$The set of points in $P$ sorted in increasing order of the $x$ co-ordinate.
$P_y$The set of points in $P$ sorted in increasing order of the $y$ co-ordinate.
$Q$The set of first $\lceil n/2\rceil$ points in $P$ (based on $x$-coordinate values).
$R$$R=P\setminus Q$
$(q_1,q_2)$Closest pair of points in $Q$.
$(r_1,r_2)$Closest pair of points in $R$.
$\delta$$\delta=\min(d(q_1,q_2),d(r_1,r_2))$
$(x^*,y^*)$$(x^*,y^*)=P_x\left[\lceil \frac{n}{2}\rceil\right]$
$S$Set of points $\{(x,y)\in P| |x-x^*|\le \delta\}$.