Overview

• Different algorithms can be appropriate in different situations
• Different internal representations can have different levels of complexity

Criteria for comparing implementations/algorithms

• Execution time
  • linear search vs binary search
• Memory required
  • Most sorts are in-place vs merge sort (basic version requires second array)
• Data movements
  • bubble sort (constant swapping) vs selection sort (single swap at end of pass)
  • In Java, anything big is typically an object, and what is moved around is the reference; a relatively small value

Factors affecting algorithm and performance

• Size of problem
  • number of elements to be sorted or in container
• Nature of data
  • ascending sorted, descending sorted, random

Algorithmic Analysis

• Study of the running time ((time) efficiency) and storage requirement (space efficiency) of an algorithm
• Not interested in CPU clock time, but something relative to the size of the input to the algorithm
  • Moore's Law makes the 'clock' speed a moot point.
• Introduce the notion of order of an algorithm and Big O notation as a vocabulary to talk about such efficiency issues.

Some Examples

Linear Search of an Array

bool linearSearch(int arr, int n, int val) {
	for (int i = 0; i < n; i++)
		if (arr[i] == val) return true;
	return false;	
}

• Running time increases with size of the array (n)
• In particular the number of comparisons is proportional to n
• We say the algorithm is linear, and of order n

Simple-minded Bubble Sort of an Array

void bubbleSort(int arr, int n) {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n-1; j++)
			if (arr[j] > arr[j+1]) {
				int t = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = t;
			}
}

• Running time also increases with n...
• But now, the number of comparisons is proportional to n²
  • The outer loop is executed n times and the inner loop is executed n-1 times for each outer loop iteration, resulting in n * (n-1)n² - n
  • This value is proportional to n2.
• We say the algorithm is quadratic, and of order n²

Selection Sort of an Array

void selectionSort(int arr, int n) {
	for (int last = n-1; last > 0; last--) {
		int maxPos = 0;
		for (int j = 1; j < last; j++)
			if (arr[j] > arr[maxPos]) maxPos = j;
		int t = arr[maxPos];
		arr[maxPos] = arr[last];
		arr[last] = t;
	}
}

• The number of comparisons is still proportional to n²
  • The inner loop is executed n-1 + n-2 + n-3 + .... + 3 + 2 + 1 times = n(n-1)/2 times = (n2 - n)/2 times
• The algorithm is also quadratic (order n²)
  The above uses the equality

  sum(1 … n) = n(n+1)/2
  				

  (for sum(1 …) this translates to (n-1)n/2

  The following is not a proof but a visual representation of the above; the red dots form the sequence 1, 2, 3, 4, 5 (each row) and similarly form slightly over half (i.e., the black dots cover the diagonal; which is why it's n+1) of a square of side 5

  .....
  .....
  .....
  .....
  .....
  					

  Proofs of the equality:

  • Algebraic:

        sum =  1  +  2  +  3  + … + n-2 + n-1 +  n
      + sum =  n  + n-1 + n-2 + … +  3  +  2  +  1
    ------------------------------------------------------
    2 * sum = n+1 + n+1 + n+1 + … + n+1 + n+1 + n+1
    =
    2 * sum = n(n+1)	// there are n vertical pairs in the above equation, each adding up to n+1
    =
        sum = n(n+1)/2
       					

  • Inductive:
    • First we show it true for n=1

      1 = 1*2/2 
      							

      i.e., sum(1 … 1), i.e., 1, is indeed equal to 1*2/2
    • Now assume the equality is true for n, i.e.,

      sum(1 … n) = n(n+1)/2
      							

      we show it true for n+1, i.e., that

      sum(1 … n+1) = (n+1)(n+2)/2
      							

      First, pull the n+1 term out of the sum on the left hand side, leaving a summation from 1 … n

      sum(1 … n+1) = sum(1 … n) + n+1
      									

      The remaining summation — sum(1 … n) is our inductive hypothesis (i.e., the equation we're trying to prove and which we assumed was true for n; this exact case). We apply the equality to this summation:

      sum(1 … n) + n+1 = n(n+1)/2 + n+1
      									

      and we now set up for an add, by adding in the denominator 2 for the n+1 term):

      n(n+1)/2 + n+1 = n(n+1)/2 + 2(n+1)/2 = n2/2 + n/2 + 2(n+1)/2 
      									

      we distribute (split) the 2(n+1)/2 term:

      n(n+1)/2 + n+1 = n(n+1)/2 + 2(n+1)/2 = n2/2 + n/2 + 2n/2 + 2/2 
      									

      combine the like terms (the n/2's):

      n2/2 + n/2 +2n/2 + 2/2 = n2/2 + 3n/2 + 2/2
      									

      and finally, factor out the quadratic in the numerator:

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

      We thus have

      sum(1 … n+1) = (n+1)(n+2)/2 
      							

      i.e., the induction is proved, and thus the equality is true

Binary Search of an Array

bool binarySearch(int arr, int lo, int hi, int val) {
	if (lo > hi) return false;
	mid = (lo + hi) / 2;
	if (arr[mid] == val) 
		return true;
	else if (arr[mid] < val) 
		return binarySearch(arr, mid+1, hi, val);
	else 
		return binarySearch(arr, lo, mid-1, val);
}

• Running time also increases with n...
• But now, the number of comparisons is proportional to log2n
  • Each recursive call splits the array size in half
  • Number of times the number n can be halved before reaching 0 is log₂n
• We say the algorithm is logarithmic, and of order log₂n

Accessing the i'th Element of an Array

int arr[10];
…
… = arr[i];
…

• Running time is independent of n...
  • To get to the i'th element: &arr[i] ↔ arr + i → starting-addresss-of-arr + (i * size of each elemenet) (scaled pointer arithmetic)
• We say the algorithm is constant, and of order 1

Finding the Minimum of an Unsorted Array

int getMin(int arr, int n) {
	for (int i = 1; i < n; i++)
		if (arr[i] < min) min = ar[i];
	return min;
}		

• This algorithm is linear (order n)

Finding the Minimum of an Sorted Array

int getMin(int arr, int n) {
	return arr[0];
}		

• This algorithm is constant (order 1)

Removing an Element from an Unsorted Array

int remove(int arr, int &size, int index) {
	for (int i = index; i < size-1; i++)
		arr[i] = arr[i+1];
	size--;
}

• What about doing it this way?

int remove(int arr, int size, int index) {
	arr[index] = arr[size-1];
	size--;
}

Observations

• Note the order can be affected by:
  • The choice of data structure
    • Minimum of sorted and unsorted array
  • The choice of algorithm:
    • Linear vs binary search on an array
  • The implementation of the data structure
    • vector with add inserting at location 0 of the array, rather than at end of the array
• The above are not independent
  • Binary search is not a choice if the array is not sorted

Big O Notation

• When determining the order of an algorithm, we're interested in the dominant term of the expression for the running time.

  n2 - n + 1
  	

  has n² as the dominant term.
• Furthermore, from a theoretical standpoint, we're not interested in coefficients either.
  • This is because from a theoretical point of view, we're in retested in the running time as a function of the size of n, and we therefore take n to infinity.

  30n3
  	

  as n grows larger, the n³ quickly outstrips the 30 coeeficient.
• The order of an algorithm is (loosely speaking) the (coefficient-less) dominant term of the running time expression, and is denoted by embedding it in O( ) which is called Big O notation. Thus a linear order algorithm would be denoted as O(n) and, as we mentioned before, is said to be either of order n or of linear order

Common Orders

Comparing the Orders and their Growths

Here

• The first graph shows a tables of values of the various orders for powers of two up to 2²⁰ (~1,000,000)
• The next several graphs show adjacent orders for those values.
  • Other than the first (O(1) vs O(logn), the spread is too wide so the smaller order comes off as a flat line. To illustrate the relative growth, a second graph is displayed, with a logarithmic y axis, allowing for a better view of the two lines of the graph.
• The final graphs display the various coefficients relevant to each order and their effect on the values/graphs.
  • The takeaway from these is to see how while the coefficients affect the shape of the graph, the graph still follow similar contours.

Here is a series of graphs to help get a better sense of the relative growth of the above values (and therefore the relative performances of algorithms of the various orders), and the relative effect of coefficients on the adjacent orders.

• The first graph simply displays the five orders on the same chart
• Each of the successive sheets compares a pair of relevant orders using three graphs:
  • #1 illustrates the natural value, i.e., the functions without any coefficients. This gives a simple view of the relative growth of the functions.
  • #2 presents a comparison of the two with the lower/smaller order having a high coefficient (i.e., a lot of operations in the inner loop of an algorithm of that order). The coefficient is also chosen so that the graphs cross each other in the given range.
    • The idea is to show
      • given a large enough coefficient, the lower function can for a while have a greater value then the higher function
      • no matter what the higher function will eventually catch up
  • #3 has the lower function still with the high coefficient and now the higher function has been itself diminished with a small coefficient. It may be difficult to envision or project the graph to the right in your mind, but #2 shows you how the higher function 's growth is such that it will eventually catch up (and despite what it may look like in #3, that is true regardless of how small a coefficient we provide).
• Only some of the pairs of orders are compared. In general, in a data structures context, we are primarily interested in adding to, removing from, and searching a collection of elements; as well as sorting the elements.
  • A single add, remove and search each typically involve at most a pass over the entire collection, for which a single loop of n iterations suffices (where n is the number of elements in the collection), and thus while we might hope for an algorithm that is better than linear (O(n)), we don't expect to do worse. As such, when searching, the relevant orders seem to be constant, logarithmic and linear.
  • The above three operations are repeated on a container and in particular we might want to ask what the performance is to create a container of n elements in the first place, i.e., to perform n adds, and thus we might want to compare n add with a cost of log(n) per add (i.e., O(nlog(n))) with n adds with a cost of n per add (O(n²)).
  • Sorting — at least what we've seen of it up to now — consists of making successive passes through the array (or some other collection) and during each pass doing something to improve the sortedness of the array (swapping out of order adjacent elements in bubble sort, or moving the largest element to the end for selection sort). A pair of nested loops is a natural outcome: each pass require a loop to move through the array, and repeated passes involves a secnd outer loop to repeat the process. Again, the inner loop moves through n elements, and the outer loop repeats this process n times. (There's some hand-waving here, but it's clear that for selection sort, after the largest element is moved, we need to do the same for the next largest element, and so on for each of the n elements; bubble sort is not as clear, ut if you think of the largest element bubbling to the end of the array, the the next largest, it too requires n successive passes). We thus expect our sort to be no worse than quadratic (O(n²), however we hope to do better. The immediate predecessor to quadratic in the order hierarchy is loglinear (O(nlog(n))), so we do that comparison as well. (We don't bother going any lower as there's a theoretical result — that we'll simply present as true — that tells us sorting can't be done any faster.)
  • So while one COULD compare any pair of orders, based upon the above discussion, only a few are actually relevant:

    constant (O(1)) vs logarithmic (O(log(n)))	We've already seen that finding the maximum of a sorted array is of constant (O(1)) order. We will eventually encounter a data structure that will allow us to find a maximum element n logarithmic (O(log(n))) time. Similarly, we've already seen that binary search operates in logairthmic time. We will also encounter a data strcutures that aspires to constant time searches.
    constant (O(1)) vs linear (O(n))	Unsorted lists do not allow for binary searching, so we're stuck with linear search. We've already seen that binary search operates in logarithmic time. We will also encounter a data structures that aspires to constant time searches. Finding the max/min of an unsorted list is linear, whereas if the list is sorted, the max/min is constant.
    logarithmic (O(log(n))) vs linear (O(n))	Binary vs linear search We will also encounter other relatively similar containers, one of which forces a linear search, while the other allows for a binary search of sorts (in the same manner that an unsorted array requires a linear search while a sorted one can use binary search).
    loglinear (O(nlog(n))) vs quadratic	Performing n linear vs n binary searches We will be covering the various sorts, some are qudratic others loglinear.

Amortized Time

• What is the cost of appending an element to a resizeable Vector object (i.e., calling add)?
  • Typically constant — accessing any element of the (underlying) array is constant time
    • a[i] = *(a+i) (scaled: *(a + i * element size)
  • Adding to the end (appending) requires no sliding of elements and thus that is also a constant operation (assigning the element to the next empty location and incrementing the size)
• What happens when the array has to be resized?
  • If we double the capacity of the vector
    The resizing becomes linear (proportional to n — the number of elements)
    • However, this only occurs after n insertions
      • Averaged out this only adds 1 (a constant cost) to each append operation
  • OTOH, if we increase the capacity by 1, this doesn't happen, rather our cost explodes

Summary (Yanosky's 4 Rules)

• Coefficients don't count
• The dominant term is all that counts
• Small numbers don't count
• Hardware doesn't count

An Algorithmic Analysis Cheat Sheet