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

**$O(\log($min$(a,b)))$**

### Divide and Conquer

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

__Binary Search__

__Binary Exponentiation__

__Merge Sort__**(merging step)**:

**L-M call**)

**M-R call**)

**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}.

**$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}.

**$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).

**$a$ gets transformed: {2,5,7,7,3,6,8} $\rightarrow$ {2,3,5,6,7,7,8$}.**

**1.**$13=2\times7-1$ and the array was of size $7$. Is it some coincidence? No. Try to prove that the total number of "bodies" that would be created would be $2n-1$ where $n$ is the size of the input array.

**2.**For a body $i$, denote its path distance from body $1$ by $d(i)$. For eg. in the above diagram $d(7)=3$,$d(13)=2$,$d(1)=0$,etc. Prove that $\sum_{d(i)=c} (r_i-l_i+1)=n$ for all distinct possible values of $c$. Now, in each body you do the merging step atmost once and copy some array into another array. So basically you do atmost $c(r-l+1)$ steps for some constant $c$.So using the summation you proved above and this fact, can you see why this algorithm is $O(n\log n)$? Hint:What is the approximate maximum possible value of $c$?

#### Sieve of Eratosthenes

**$j$ is a prime**. So we are roughly doing $n(\sum \frac{1}{p})$ steps in this algorithm where the summation is over all $p<n$. A result in analytical number theory tells that the summation roughly approaches $\log \log(n)$ for large $n$ Hence the complexity of the algorithm is $O(n\log (\log(n)))$.

**Problem 1:**

__Solution:__

__Comment:__

**Problem 2:**

__Solution:__

__Comment:__

**Problem 3 (USAMO 2002):**

__Solution:__

__Comment:__

**Problem 4 (APMO 2017):**

__Solution:__

__Comment:__

__A pictorial representation of the transformation sending $x$ to $y$.__

**Problem 5(Based on the Codeforces problem GCD Guess)**

__Solution:__

__C__onsider a variable $y$ initially set to $0$ We think of $x$ in terms of its binary representation. We iterate a variable $i$ from $1$ to $t$ and after every iteration, we would have successfully determined the $i$th bit from the right.

__Comment:__

## Comments

## Post a Comment