### Logs and Bits

This blog can be divided into two parts: In the first part, I would be talking about some basic but useful $\log n$-ish algorithms, and later I would be discussing some construction-based problems whose solution exploits the binary representation of numbers. Both parts can be read independently too.

Let's get started...

For completeness, I define what is an algorithm: A finite sequence of well-defined mathematical or logical steps that when followed would yield an answer to a class of similar problems or a computation. Iteration and Recursion lie at the core of any algorithm. The time complexity of an algorithm is an estimate of how the number of steps in the algorithm grows as the input increases. So we say an algorithm is $O(n)$ if the number of steps in it is bounded above by $cn$ for some $c$.And similarly, you understand $O(\log n)$,$O(n^2)$,etc.

The main purpose of an algorithm is to shorten the number of steps or the memory used in the otherwise brute-force or naive approaches to that problem. A simple example to give is of finding if a subset of $N$ elements has some subset whose elements sum up to a given number $S$. The brute-force method is to list down all the $2^N$ subsets of the set, find the sum for each of them and check if it equals $S$.But there is a different approach that uses at most $N\times S$ steps and is known as the Subset Sum Problem.

There are numerous $log(n)$ algorithms in use today, but I think there are these three core algorithms that form the foundations of almost all others:

### Euclid's GCD algorithm

We are asked to find the greatest common divisor of two given positive integers $a$ and $b$ and $a>b$.What is your brute-force approach? I guess it would be iterating over all $g<=b$ and if $g\vert a$ and $g\vert b$ you update $g$ as your answer. But a much better method was proposed by Euclid:
Let $r_0=a$ and $r_1=b$. For $i\geq 2$ define $r_{i}$ and $q_{i-1}$ iteratively as follows:
$$r_{i-1}=q_ir_i+r_{i+1}$$ where $0\leq r_{i+1}<r_i$. Stop this iteration as soon as $r_{n}=0$ for some $n$.Then the gcd is $r_{n-1}$.

The proof of this is simple:  Since gcd$(a,b)$=gcd$(a-kb,b)$ for all integers $k$,
gcd$(r_i,r_{i+1})$=gcd$(r_i-q_{i+1}r_{i+1},r_{i+1})$=gcd$(r_{i+2},r_{i+1})$.
Therefore gcd$(a,b)$=gcd$(r_{n-1},r_{n})$=gcd$(r_{n-1},0)$=$r_{n-1}$.

Now observe that $\forall i \leq n$  $r_{i-2}=q_{i-1}r_{i-1}+r_i \geq r_{i-1}+r_i > 2r_i$.
Therefore if $n$ is even, $2^{\frac {n-2}{2}}r_{n-1}\leq r_1 =b$ else $2^{\frac{n-3}{2}}r_{n-1}\leq r_1=b$
In short $n\leq c\log_{2}{\frac{b}{r_{n-1}}}\leq c\log_{2}b$ for some $c$.
Thus the complexity of this $O(\log($min$(a,b)))$

Following is the pseudo-code of the algorithm:

Execute this loop while $b>0$
Define variable  $q=\lfloor\frac{a}{b}\rfloor$
Define variable $b'=b$
Change the value of variable $b$ to $a-bq$
Change the value of variable $a$ to $b'$

Here, after the $i$th iteration the values assumed by $a$ and $b$ are same as $r_i$ and $r_{i+1}$ respectively. The loop is executed $n-1$ times and the value of $a$ thus obtained is the gcd.

Also for the connection of  Euclid's GCD algorithm with Bezout's theorem, check this out: Extended Euclidean Algorithm

Would Euclid have thought about how effective how his method was when it was discovered thousands of years before the notion of complexity was introduced?

### Divide and Conquer

'Divide and Conquer is an umbrella term that I assign to three important algorithms:

Binary Search
You are given a sorted list of $N$ distinct numbers and additionally a number $A$.You need to find whether $A$ is in the list or not.If N is small you can just tell by inspection.  But here we are given a large N. Obviously, the naive approach is to check the numbers of the list one by one and check if any of them is equal to $A$ There is indeed a much better approach. Denote by $a[i]$ the $i$th smallest number in the list. Declare two variables $l$ and $r$ where initially $l=1$ and $r=N$. Here is the pseudo-code for binary search:

Execute the loop till $l<r$ holds:
declare a variable $m=\lfloor\frac {l+r}{2}\rfloor$
if($a[m]<A$)
change the value of $l$ to $m+1$
else if($a[m]\geq A$)
change the value of $r$ to $m$

if($a[l]$ is equal to $A$)
$A$ is present in the list
else
$A$ is not present in the list.

Why does this work? The main observation is that after every step if $A$ exists then it has to satisfy $A=a[i]$ where $l\leq i\leq r$.We prove this by induction.
At the first step, it is trivial as we have initialized $l$ and $r$ as the boundaries of the list.
So assume it is true till $k$ steps. So suppose in the $k$th iteration we find $A>a[m]$.It means that $A>a[i] \forall i: l\leq i\leq m$ (sorted list).By induction hypothesis we know that if $A$ exists then $A=a[i]\forall i:l\leq i\leq r$. These two facts imply that if $A$ exists then $A=a[i]$ for some $m+1\leq i\leq r$ .But the $l$ and $r$ after the $(k+1)$th step are $m+1$ and $r$ respectively after the $k$th step by our algorithm. Thus proved. The case $A\leq a[m]$ can be dealt along the same lines.
And why is this log$(n)$? The value of $(r-l)/2$ roughly halves after each loop execution. Thus it would reach $0$ in roughly $log_2 n$ moves. Hence it is $O(\log n)$.

Binary Exponentiation
Given a real $x$ and a natural $n$, you need to evaluate $x^n$.Obviously for small values of $n$ you can do it by hand or with a calculator. But what if I asked you to evaluate $2^{10^{10}}$ modulo some large prime under $1$ second? You would require the help of a computer and an efficient algorithm too. The brute-force approach is of multiplying $1$ by $x$ $n$ times. The clever approach uses recursion. In order to get a feel of recursive programs in case you are unfamiliar with it, refer to Fibonacci number recursion. Here is the pseudo-code of binary exponentiation:

solve(Base $x$, exponent $n$)(This function would return the value of $x^n$)
if($n$ equals $0$)
return $1$ from this function.
else
Define a variable $z =$ solve(Base $x$, exponent $\lfloor\frac{n}{2} \rfloor$)
if($n$ is odd) return $xz^2$
else return $z^2$

I think you might have already guessed the logic of this algorithm. It is just precomputing $x^{\lfloor\frac {n}{2}\rfloor}$ and expressing $x^n$ in terms of it. As to why this is logarithmic, the size of the exponent roughly halves after each function call, hence the exponent would reach $0$ in approx $log_{2} n$ steps. Thus the complexity is $O(\log n)$.

Merge Sort
Given an array(just a list) of $N$ numbers, you need to sort them in increasing order. First of all, this algorithm is not $O(\log n)$ but $O(n\log n)$, but its significance and method deserves its mention here. This algorithm is also of recursive nature. Denote by $a[i]$ the $i$th number in the array from the left and call $i$ as this number's index. Define two variables $l$ and $r$ where initially $l=1$ and $r=n$. The idea is this:

For the current value of $l$ and $r$ define $m=\lfloor\frac{l+r}{2}\rfloor$.Now construct two arrays $b_1$ and $b_2$ of sizes $m-l+1$ and $r-m$ respectively such that $b_1$ contains the elements of $a$ having index in the range $[l,m]$ placed in increasing order from left to right and $b_2$ be similarly defined for the index range $[(m+1),r]$. Now you create three variables $i$,$l_1$ and $r_1$ and an empty array $c$ of size $(r-l+1)$ where initially $l_1=l$,$r_1=m+1$ and $i=1$.You perform the following operation(merging step):

Execute this loop while either $l_1<=m$ or $r_1<=r$
If($l_1$ is equal to $m+1$)
Execute this loop while $r_1<=r$
Set $c[i]$ equal to $b_2[r_1]$
Increase $r_1$ by $1$
Increase $i$ by $1$

Else If($r_1$ is equal to $r+1$)
Execute this loop while $l_1<=m$
Set $c[i]$ equal to $b_1[l_1]$
Increase $l_1$ by $1$
Increase $i$ by $1$

Else If($b_1[l_1]>b_2[l_2]$)
Set $c[i]$ equal to $b_2[l_2]$
Increase $l_2$ by $1$
Increase $i$ by $1$

Else
Set $c[i]$ equal to $b_1[l_1]$
Increase $l_1$ by $1$
Increase $i$ by $1$

So let me illustrate the above code with an example.

Suppose at some random stage of the algorithm, $b_1=${$2,5,7,7$},$b_2=${$3,6,7,8$}, $c=${}, $l=l_1=3$ ,$m=6$, $r_1=7$, $r=10$ $i=1$ and merging step needs to be performed on $b_1$ and $b_2$:
After iteration $1:$ $c=${$2$},$l_1=4$,$r_1=7$ $i=2$ and others as it is.
After iteration $2:$ $c=${$2,3$},$l_1=4$,$r_1=8$ $i=2$ and others as it is.
After iteration $3:$ $c=${$2,3,5$},$l_1=5$,$r_1=8$ $i=3$ and others as it is.
After iteration $4:$ $c=${$2,3,5,6$},$l_1=5$,$r_1=9$ $i=4$ and others as it is.
After iteration $5:$ $c=${$2,3,5,6,7$},$l_1=6$,$r_1=9$ $i=5$ and others as it is.
After iteration $6:$ $c=${$2,3,5,6,7,7$},$l_1=7$,$r_1=9$ $i=6$ and others as it is.
After iteration $6:$ $c=${$2,3,5,6,7,7,7$},$l_1=8$,$r_1=10$ $i=7$ and others as it is.
After iteration $6:$ $c=${$2,3,5,6,7,7,7,8$},$l_1=8$,$r_1=11$ $i=8$ and others as it is.
And the loop terminates.

So what have we obtained? $c$ just contains the union of elements in $b_1$ and $b_2$ and they are arranged in increasing order and the main loop was iterated atmost (r-l+1) times. This was the key step in the merge sort algorithm. Now to the main algorithm:

Mergesort(Given $l$ and $r$ and array $a$)
If($l$ is not equal to $r$)
Define a variable $m=$ $\lfloor \frac{l+r}{2}\rfloor$
Mergesort(Given $l$ and $m$ and array $a$)            (Denote this by L-M call)
Mergesort(Given $m+1$ and $r$ and array $a$)        (Denote this by M-R call)
Declare an array $b_1$ of size $(m-l+1)$
Declare an array $b_2$ of size $(r-m)$
Copy elements in $b_1$ from $a$ such that $b_1[i]=a[i+l-1]$
Copy elements in $b_2$ from $a$ such that $b_2[i]=a[m+i]$
Declare an array $c$ of size $r-l+1$,initially empty.
Declare three variables $i=1$,$l_1=l$ and $r_1=m+1$
Carry out the merging step for $b_1$ and $b_2$ with the help of $c$,$i$,$l_1$ and $r_1$.
.
.
.
Copy elements in $a$ from $c$ such that $a[i]=c[i-l+1]$

If you are a newbie to recursion, understanding this in the first go might not be easy, so let's try to understand the entire algorithm with the help of an example: $a=$ {7,5,7,2,3,8,6} Let Body $i$ denote the execution of the algorithm inside the $i$th call of the function.

Body 1: $l=1$, $r=7$ and $m=4$. L-M call is made for $l=1$ and $r=4$ (goes to Body 2).
Body 2: $l=1$, $r=4$ and $m=2$. L-M call is made for $l=1$ and $r=2$ (goes to Body 3).
Body 3: $l=1$, $r=2$ and $m=1$. L-M call is made for $l=1$ and $r=1$ (goes to Body 4).
Body 4: $l=1$, $r=1$.Here $l$ is equal to $r$, so return to the body from which it was called (Body 3).
Body 3: L-M call is completed. M-R call is made for $l=2$ and $r=2$ (goes to Body 5).
Body 5: $l=2$, $r=2$.Here $l$ is equal to $r$ so return to the body from which it was called (Body 3).
Body 3:M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {7} and $b_2=${5}. $c$ is declared and empty. Applying  the merging step, $c=${$5,7$}.The elements of $c$ are copied in $a$. So $a$ gets changed to {$5,7,7,2,3,8,6$}.Body 3 is completed, return to the body from which it was called (Body 2).
$a$ gets transformed: {7,5,7,2,3,8,6} $\rightarrow$ {5,7,7,2,3,8,6}.
Body 2:L-M call is completed. M-R call is made for $l=3$ and $r=4$ (goes to Body 6).
Body 6: $l=3$, $r=4$ and $m=3$. L-M call is made for $l=3$ and $r=3$ (goes to Body 7).
Body 7: $l=3$, $r=3$.Here $l$ is equal to $r$, so return to the body from which it was called (Body 6).
Body 6: L-M call is completed. M-R call is made for $l=4$ and $r=4$ (goes to Body 8).
Body 8: $l=4$, $r=4$.Here $l$ is equal to $r$, so return to the body from which it was called (Body 6).
Body 6: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=${7} and $b_2$={2}. $c$ is declared and empty. Applying the merging step, $c=$ {2,7}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$5,7,2,7,3,8,6$}. Body 6 is completed, return to the body from which it was called (Body 2).
$a$ gets transformed: {5,7,7,2,3,8,6} $\rightarrow$ {5,7,2,7,3,8,6}.
Body 2: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {5,7} and $b_2=${2,7}. $c$ is declared and empty. Applying the merging step, $c=$ {2,5,7,7}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$2,5,7,7,3,8,6$}. Body 2 is completed, return to the body from which it was called (Body 1).
$a$ gets transformed: {5,7,2,7,3,8,6} $\rightarrow$ {2,5,7,7,3,8,6}.
Body 1: L-M call is completed. M-R call is made for $l=5$ and $r=7$ (goes to Body 9).
Body 9: $l=5$, $r=7$ and $m=6$. L-M call is made for $l=5$ and $r=6$ (goes to Body 10).
Body 10: $l=5$, $r=6$ and $m=5$. L-M call is made for $l=5$ and $r=5$ (goes to Body 11).
Body 11: $l=5$, $r=5$. Here $l$ is equal to $r$, so return to the body from which it was called (Body 10).
Body 10: L-M call is completed. M-R call is made for $l=6$ and $r=6$ (goes to Body 11).
Body 12: $l=6$, $r=6$. Here $l$ is equal to $r$, so return to the body from which it was called (Body 10)
Body 10: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {3} and $b_2=${8}.
$c$ is declared and empty. Applying the merging step, $c=$ {3,8}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$2,5,7,7,3,8,6$}. Body 10 is completed, return to the body from which it was called (Body 9).
$a$ gets transformed: {2,5,7,7,3,8,6} $\rightarrow$ {2,5,7,7,3,8,6}.
Body 9: L-M call is completed. M-R call is made for $l=7$ and $r=7$ (goes to Body 13).
Body 13: $l=7$,$r=7$. Here $l$ is equal to $r$, so return to the body from which it was called (Body 9).
Body 9: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {3,8} and $b_2=$ {6}.
$c$ is declared and empty. Applying the merging step, $c=$ {3,6,8}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$2,5,7,7,3,6,8$}. Body 9 is completed, return to the body from which it was called (Body 1).
$a$ gets transformed: {2,5,7,7,3,8,6} $\rightarrow$ {2,5,7,7,3,6,8}.
Body 1: M-R call is completed. Thus $b_1$ and $b_2$ are declared. $b_1=$ {5,7,2,7} and $b_2=$ {3,6,8}. $c$ is declared and empty. Applying the merging step, $c=$ {2,3,5,6,7,7,8}. The elements of $c$ are copied in $a$. So $a$ gets changed to {$2,3,5,6,7,7,8$}. Body 1 is completed, return to the body from which it was called (Nothing).