There is a group of algorithms that require O(logN) operations. They are based on subsequently reducing the problem by a factor of two. Such algorithms are called divide-and-conquer algorithms.

1. Binary Search

Given an integer X and integers A0, A1, … An-1, which are presorted and in memory,
find i such that A_i = X, or return i = - 1 if X is not in the list A0, A1, .. An-1.

Solution 1: Scan all elements from left to right, each time comparing with X.
This algorithm requires O(N) operations.
It does not take advantage of the fact that the list of integers is sorted.

Solution 2:

Find the middle element A_mid in the list and compare it with X

If they are equal, stop (the element is found)

If X < A_mid consider the left part of the list and repeat the above operations

If X > A_mid consider the right part of the list and repeat the above operations.

When the list is reduced to one element not equal to X, return NOT FOUND

Example:

Look for 7 in the following list: 1, 7, 8, 10, 13, 17, 20, 21

1. A_mid = 13, 7 < 13, consider 1, 7, 8, 10
2. A_mid = 8, 7 < 8, consider 1, 7
3. A_mid = 7, 7 = 7, the element is found

Each next list whose middle element is compared with X is half the size of the previous list,
thus the number of the comparisons is logN, where N is the size of the original list.

Other examples of divide and conquer algorithms are the Euclid's algorithm for finding
the greatest common divisor and the algorithm for computing X^N.

2. Euclid's Algorithm for finding the greatest common divisor

The algorithm is based on the observation that the GCD (greatest common divisor) of two integer numbers M and N, M > N, is the same as the GCD of N and the remainder of the integer division M / N.

Recursion:

gcd (long M,long N)
{
   if (M%N == 0), return N;
   else return gcd(N, M%N);
}

The algorithm works by computing remainders. The last non-zero remainder is the answer. Here is a non-recursive implementation of the algorithm:

long gcd ( long m, long n)
{
  long rem;
  
  while (n != 0)
	{
	   rem = m % n;
	     m = n;
	     n = rem;
	}
   return m;
}

Note that while the algorithm is recursive, its implementation above is a non-recursive one,
very similar to the non-recursive computation of Fibonacci numbers.

Complexity: O(logN)

We can prove that given M > N, the remainder M mod N is at most M/2.

1. case 1: N £ M/2. Since the remainder is less than N, it would be less than M/2
2. case 2: N > M/2. In this case the remainder would be M - N, and since N > M/2, M - N would be less than M/2.

After two iterations the remainder appears in the first column, so after two iterations the remainder would be half of its original value. Hence the number of iterations is at most 2logN, i.e. O(logN)

Example:

M = 24, N = 15


3. Exponentials

The algorithm is based on the recursive definition of X^N :

X^N = (X²)^N/2*X if N is odd

X^N = (X²)^N/2 if N is even

long pow (long x, int n)
{
	if ( n == 0) 		return 1;
	if ( n == 1)		return x;
	if (isEven( n )) 	return     pow ( x * x, n/2);
        else                    return x * pow ( x * x, n/2);
}

In each next recursive call we reduce the power by a factor of two. The operations are at most 2logN, accounting for the cases when N is odd, i.e. O(logN)

Note, that there is another recursive definition that reduces the power just by 1:

X^N = X*X^{N -1}

Here the operations are N-1, i.e. O(N) and the algorithm is les efficient than the divide and conquer algorithm.

4. How to count operations

The following rules are generaly used when analysing code fragments

1. Single statements (not function calls) : constant O(1) = 1.

2. Sequential fragments: the maximum of the operations of each fragment

3. Single loop running up to N, with single statements in its body: O(N)

4. Single loop running up to N, with the number of operations in the body O(f(N)):

   O(N*f(N))

5. Two nested loops each running up to N, with single statements: O(N²)

6. Divide-and-conquer algorithms with input size N: O(logN)

5. Example: Relative Primes

What is the probability for two numbers less than N to be relatively prime ?
( e.g 7 and 9 are relatively prime, gcd(9,7) = 1)

Probability = (number of prime pairs) / (number of all pairs)

Count the operations in the following function:

double probRelPrime (int n)
{
  int rel = 0, tot = 0;	// rel - number of prime pairs
			// tot - number of all pairs
					
  int i, j;
  
  for ( i = 0; i <=n, i++)
   for (j = i+1; j <= n; j++)
    	{
		tot++;

		if (gcd(i,j) ==1)  rel++;
   	}
  return (double) rel/tot;
}

Here we have:

• Two nested loops each runs up to N.
• The body contains a function with complexity O(logN).

Hence the complexity of probRelPrime is O(N² * logN)