CS 201 - 10/21/14 Run Time of Algorithms Classifications of Run Time (based on N data points) 1 or Constant Time log log N log N N N log N N * N (N^2) N * N * N (N^3) ... Exponential (2^N) An algorithm is O( NlogN ) "order of" or "big-Oh of" Code for Binary Search (assumes array is already sorted) assume sorted integer array, arr, of N values int low, high, mid; int target; low = 0; high = N - 1; mid = (low + high) / 2; while ( ( low < high ) && (arr[mid] != target) ) { if ( arr[mid] < target ) { low = mid + 1; } if ( arr[mid] > target ) { high = mid - 1; } mid = (low + high) / 2; } What is the Big-Oh run time of a push onto a stack? O (1) or O (C) What is the Big-Oh run time of an insert into a linked-list in which values are stored in increasing order? O(N) What is the Big-Oh run time of Scalar Matrix Mulitplication? O(rows*columns) What is the Big-Oh run time of Scalar Square-Matrix Mulitplication? O( rows^2 )