CIS 121 April 19, 2000

In order to understand our discussion of the analysis of the complexity of algorithms, we need to review a few basic mathematical concepts.

If n is any positive integer, then

1 + 2 + 3 + ... + n = n(n+1)/2

It is also important to understand logarithms. The concept of a logarithm is a very ingenious one. Its major feature is that it turns multiplication into addition. The reason for this is the following very simple law.

aⁿ*a^m=a^m+n

A logarithm is actually an exponent. Associated with a logarithm is a number called its base. The logarithm of a number to a certain base is the exponent to which we must raise the base to achieve the number. For example,

10²=100 and 10³=1000

So the logarithm of 100 base 10 is 2, and the logarithm of 1000 base 10 is 3.

Another important base is 2. This base is important because much of what we do in computers involves the binary system in which there are two digits, 0 and 1.

Another important fact about logarithms is the change of base formula.

log_an = log_bn/log_ba

Notice that log_ba is a constant with respect to n.

Recall that the natural logarithm is the logarithm whose base is the number e. We normally omit the base when we refer to logarithms base e.

When we analyze an algorithm, we try to measure how much time it will take the algorithm to complete as a function of the number of items in the construct in question, for example the number of elements in an array. To establish a mechanism for measuring algorithms, we make the following definition.

What this definition says is that a function f(x) is bounded above by a contant multiple of g(x) as the value of x tends to infinity. That is, in the long run, f(x) is bounded above by a constant multiple of g(x).

This is read as "f is big O of g". Keep in mind that this only measures the behavior of the functions in the long run and does not tell us anything about the behavior of the function for small values of x. For example, in the long run n² is larger than 1000000n, but in the short run it is not.

Before we try to analyze the efficiency of algorithms we need to establish some basic facts about the big O notation.

What this theorem tells us is that big O is similar to an ordering. It doesn't necessarily give us the best bound. For example, if a function is O(N), it is also O(N²).

What this theorem tells us is that in the long run the largest function dominates and we can ignore smaller terms.

O(1)

The graph of constant complexity is the following.

It is a horizontal line.

O(log N)

The Binary Search Algorithm

public class BinarySearch {
   int[] array;

   public BinarySearch(int[] array) {
      this.array = array;
   }

   public int binary(int key,int first,int last) {
      if (first > last) 
         return(array.length);
      else {
         int index = (first+last)/2;
         if (array[index]==key)
            return(index);
         else if (array[index]>key) 
            return(binary(key,first,index-1));
         else
            return(binary(key,index+1,last));
      }
   }

   public int search(int key) {
      return(binary(key,0,array.length-1));
   }

   public static void main(String[] args) {
      int[] array = {5,7,10,13,18,20,21};

      BinarySearch myBinarySearch = new BinarySearch(array);

      System.out.println(myBinarySearch.search(5));
      System.out.println(myBinarySearch.search(21));
   }
}

BinarySearch.java

Analysis of the Algorithm

We assume the array is sorted. The algorithm works by halving the array in which we are searching. We examine the element in the middle of the array to see if it is the element we are looking for. If it is not then we compare the values, and if the element we are looking for is "smaller" than the one in the middle, then we search in the left subarray. If the element we are looking for is "larger" than the one in the middle, then we search in the right subarray.

In order to obtain a big O estimate for how long this algorithm will take to complete, let us consider the number of times we must halve an array and search on one side or the other. That is we want to determine how many different arrays we will examine before we get to a one-element array. Notice that we are starting out with N elements in the array. The next we examine will have N/2 elements. As we proceed with the algorithm this pattern continues until we get to an array with one element in it.

That is the lengths of the arrays which we examine as we proceed through the algorithm are

N  N/2  N/4  ...  1

It is not easy to determine the number of arrays we must examine. However if we look at the base 2 logarithm of each of these numbers, then it is easy to determine the number of steps needed on average.

log₂N  log₂N-1  log₂-2  ...  0

So, on average, we must take log₂N + 1 steps to find the element we are looking for.

The graph of the logarithm is the following.

It is a gentle curve from left to right.

When the Input Size Doubles

When the input size doubles, then the complexity factor increases by 1 since log₂(2N) = log₂2 + log₂N = log₂N + 1. So the growth in the number of steps we must take in order to find the element we are looking for is up by 1.

O(N)

The Linear Search

public class LinearSearch {
   int[] array;

   public LinearSearch(int[] array) {
      this.array = array;
   }

   public int search(int key) {
      int index = array.length;
      
      for (int i=0;i<=array.length-1;i++)
         if (array[i]==key)
            index=i;

      return(index);
   }

   public static void main(String[] args) {
      int[] array = {5,7,10,13,18,20,21};

      LinearSearch myLinearSearch = new LinearSearch(array);

      System.out.println(myLinearSearch.search(5));
      System.out.println(myLinearSearch.search(21));
   }
}

LinearSearch.java

Analysis of the Algorithm

This is a very simple algorithm that begins at the first element in the array and searches until it finds the element we are looking for. So on average we would look through N/2 of the elements, and since we can ignore constant factors in the long run, the algorithm is O(N).

The graph of O(N) is the following.

It is a non-horizontal line.

O(N log N)

The QuickSort

public class QuickSort {
   int[] array;

   public QuickSort(int[] array) {
      this.array = array;
   }

   public void swap(int i,int j) {
      int temporary = array[i];

      array[i] = array[j];
      array[j] = temporary;
   }

   public int partition(int[] array,int first,int last) {
      int pivot = array[first];
      int lo = first;
      int hi = last;

      while (lo <= hi) {
         while ((lo <= last) && (array[lo] <= pivot)) lo++;

         while (array[hi] > pivot) hi--;

         if (lo < hi) {
            swap(lo,hi);
            lo++;
            hi--;
         }
      }
   
      swap(first,hi);
      return hi;
   }

   public void quicksort(int array[],int first,int last) {
      int pivotIndex;

      if (first < last) {
         pivotIndex = partition(array,first,last);

         quicksort(array,first,pivotIndex-1);
         quicksort(array,pivotIndex+1,last);
      }
   }

   public void sort() {
      quicksort(array,0,array.length-1);
   }

   public String toString() {
      String output = "";

      for (int i=0;i<=array.length-1;i++) {
         output += String.valueOf(array[i]);
         output += "\t";
      }

      return(output);
   }

   public static void main(String[] args) {
      int[] array = {18,7,21,5,13,10,20};

      QuickSort myQuickSort = new QuickSort(array);

      System.out.println(myQuickSort);

      myQuickSort.sort();

      System.out.println(myQuickSort);
   }
}

QuickSort.java

Analysis of the Algorithm

Let us examine how this algorithm works. We pick an element of the array which we call the pivot. We locate the correct position of this pivot in the array. We do this by searching through the array, moving all elements "smaller" than the pivot to the left and all elements "larger" than the pivot to the right.

After we have the pivot element in its correct position, we then send the left subarray and right subarray to the quicksort method.

The graph of n log n is the following.

It is like a very flat parabola.

O(N²)

The Bubble Sort

public class BubbleSort {
   int[] array;

   public BubbleSort(int[] array) {
      this.array = array;
   }

   public void swap(int i,int j) {
      int temporary = array[i];

      array[i] = array[j];
      array[j] = temporary;
   }

   public void sort() {
      int i;
      int j;

      for (i=0;i<=array.length-1;i++)
         for (j=i+1;j<=array.length-1;j++)
            if (array[j]<array[i])
               swap(i,j);

   }

   public String toString() {
      String output = "";

      for (int i=0;i<=array.length-1;i++) {
         output += String.valueOf(array[i]);
         output += "\t";
      }

      return(output);
   }

   public static void main(String[] args) {
      int[] array = {18,7,21,5,13,10,20};

      BubbleSort myBubbleSort = new BubbleSort(array);

      System.out.println(myBubbleSort);

      myBubbleSort.sort();
   
      System.out.println(myBubbleSort);
   }
}

BubbleSort.java

The graph of n² is the following.

It is a parabola.