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 )