CIS 121 April 21, 2000

Recall that we discussed some basic mathematical concepts that are necessary in studying the complexity of algorithms.

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.

On Wednesday we discussed examples of O(1), O(log N), and O(N) algorithms. We also discussed an example of an O(N log N) algorithm, the Quicksort. Let us examine this algorithm again to make sure we completely understand it.

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

Analysis of the algorithm

The algorithm is very simple. We have an outer for loop which runs from the first to the last element in the array. For each element we examine we have an inner for loop which runs through the remainder of the array. If we find an element that is smaller than the element we are examining in the outer for loop then we swap the array elements. So after the outer for loop completes we have an array sorted in ascending order.

The graph of n² is the following.

It is a parabola.

So to reiterate what we have discovered about the complexity of certain algorithms consider the following table. Notice that each of the classes we discussed also has another name.

Big O Class	Another Name	Shape of Graph	Example	Growth with double input size
O(1)	Constant Complexity	Horizontal Line	Add first two elements in an array	None! No growth
O(log N)	Logarithmic Complexity	Gentle curve up from left to right	Binary Search	Up by 1 - very slow growth!
O(N)	Linear Complexity	Non-horizontal line	Linear Search	Doubles
O(N log N)	None	Like a very flat parabola	Quick Sort	A little more than doubles
O(N²)	Quadratic Complexity	Parabola	Bubble Sort	Quadruples