Overview

• Study of the running 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.
• Introduces Big O notation as a vocabulary to talk about such efficiency issues.

Some Examples

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

bool selectionSort(int *arr, int n) {
   for (int last = n-1; last > 0; lasti--) {
      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;
   }
}
  

• Running time also increases with n...
• But now, the number of comparisons is proportional to n²
  • The inner loop is executed n-1 + n-2 + n-3 + .... + 3 + 2 + 1 times = n(n-1)/2 times = (n² - n)/2 times
  • This value is proportional to n².
  >
• We say the algorithm is quadratic, and of order n²

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;
	 if (arr[mid} & val) 
      return binarySearch(arr, mid+1+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

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

• Running time is independent of n...
  • TO get i'th element: arr + i -> starting addresss of array + i * size of each elemenet (scaled pointer arithmetic)
• We say the algorithm is constant, and of order 1

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 of order n

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

• This algorithm is of order 1

• Note the order can be affected by:
  • The algorithm:
    • Linear vs binary search on an array
  • The nature of the Data
    • Minimum of sorted and unsorted array

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 standpont, we're not interested in coefficents either.
  • This is because from a theoretical point of view, we're in terested 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