Order-of-Growth Classifications

Only a few functions really turn up when we analyse algorithms. A great number of algorithms are described by these few functions:

• Log N
• N
• N Log N
• NPOW(2)
• NPOW(3)
• 2POW(N)

When we talk about order of growth we discard the leading coefficient as an example if we hypothesize the running time of an Algorithm is N Log N what that actually means is the running time of an algorithm is C N Log N where C is some constant.

Common order-of-growth classifications

order of growth	name	typical code framework	description	example	T(2n)/T(n)
1	constant	a = b + c	statement	add two numbers	1
log N	logarithmic	while(N > 1) N = N/2	divide in half	binary search	~1
N	linear	for (int i = 0; i < N; i ++) …	loop	find the max	2
N log N	linearithmic	(see mergesort)	divide and conquer	mergesort	~2
NPOW(2)	quadratic	for(..){for(..)}	double loop	check all pairs	4
NPOW(3)	cubic	for(..){for(..){for(..)}}	triple loop	check all triples	8
2POW(N)	exponential	(see combinatorial search)	exhaustive search	check all subsets	T(N)

Problem Size solvable in minutes

growth rate	1970s	1980s	1990s	2000s
1	any	any	any	any
log N	any	any	any	any
N	millions	tens of millions	hundreds of millions	billions
N log N	hundreds of thousdands	millions	millions	hundreds of millions
NPOW(2)	hundreds	thousands	thousands	tens of thoursands
NPOW(3)	hundreds	hundreds	thousands	thousands
2POW(N)	20	20s	20s	30

Conclusion We need linear or linearithmic algorithms to keep pace with Moore’s law.

Binary Search

Fun Fact: Binary search has been notoriously tricky to get right. The first binary search was published in 1946 however the first bug-free binary search was published in 1962.

A binary search assumes a sorted data set and takes conditions to search by halving the set and comparing until there is a match or a match is not found. The key comparison operators for the target and set are.

• Lower
• Higher
• equal to
• not equal to.

Below is a standard Java implementation (Noting it’s often implemented recursively)

public static int binarySearch(int[] a, int key){
  int lo = 0, hi = a. length-1;
  while (lo <= hi){
    int mid = lo + (hi - lo) / 2;
    if      (key < a[mid]) hi = mid - 1;
    else if (key > a[mid] ) lo = mid + 1;
    else return mid;
  }
  //no match
  return -1;
}

Mathematical Analysis - Binary Search

Proposition: Binary search uses at most 1 + lg N compares to search in a sorted array of size N

Definition: T(N) = # compares to binary search in a sorted subarray of size < N

Binary search recurrence: T(N) <= T(N/2) + 1 for N > 1, with T(1) = 1

Proof Sketch (only holds if NPOW(2)):

• T(N) < = T(N/2) + 1 Given
• <= T(N / 4) + 1 + 1 Apply recurrence to first term
• <= T(N / 8) + 1 + 1 + 1 Apply reccurence to first term
• …
• <= T(N / N) + 1 + 1 + … + 1 Stop applying T(1) = 1
• = 1 + lg N

Faster Algorithm for 3-Sum

Sort based algorithm

• Sort the N (Distinct Numbers)
• For each pair of numbers a[i] and a[j] do a binary search for -(a[i] + a[j])

Analysis : Order of growth is NPOW(2) log N

• Step 1: NPOW(2) with insertion sort
• Step 2: NPOW(2) log N with Binary Search

public static int threeSum(int[] a, int target){
  n = a.length;
  // bubble sort
  for(int i = 0; i < n - 1; i ++){
    for (int j = 0; j < n - i - 1; j++){
      if(a[j] > a[j + 1])}{
        int temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }
    }
  };
  // Binary Complement search
  for ( int i = 0; i < n - 2; i ++){
    for (int j = i + 1; j < n - 1; j ++){
      int complement = target - a[i] - a[j];
      int low = j + 1;
      int hi = n - 1;
      while (low <= hi){
        int mid = low + (hi - low) / 2;
        if      (complement < a[mid]) hi = mid - 1;
        else if (complement > a[mid]) low = mid + 1;
        else return true;
      }
    }
  }
  //no match
  return false;
}