1. It's the process of determining how fast an algorithm runs and how much space it uses.
2. The goal of analyzing algorithms is to determine which ones run the fastest and use smallest of storage under some particular set of conditions.
3. For example, some algorithms work well when a collection of data is randomly organized, whereas other algorithms are only efficient when data are in sorted order.
4. One of the major objectives for this course is to develop your analysis skills so you can choose the appropriate data structures and algorithms to meet particular program specifications.

1. Algorithm analysis is mathematically based, and uses a mathematical notation.
2. The common name for it is O-notation, where the "O" stands for "order of magnitude".
   1. As the name suggests, O-notation is used to measure the broad performance of an algorithm -- i.e., the general order of magnitude of its execution time.
   2. This measure leaves out low-level details of exactly how long individual program statements take to run on particular kinds of computers.
3. Here are the formal definitions for an algorithm timing function T, for a problem of size N:
   1. T(N) = O(f(N)) if there are positive constants c and n₀ such that T(N)£ cf(N) when N ³ n₀
   2. T(N) =W (g(N)) if there are positive constants c and n₀ such that T(N) ³ cg(N) when N ³ n₀
   3. T(N) =Q (h(N)) iff T(N) = O(h(N)) and T(N) = W (h(N))
   4. T(N) = o(p(N)) if T(N) = O(p(N)) and T(N) ¹ Q (h(N))
   5. T(N) = w(p(N)) if T(N) = W(p(N)) and T(N) ¹ Q (h(N))
4. What this all means is the following:
   1. O(f(N)) is an upper bound on how much time an algorithm takes.
      1. The name for this bound is "big-Oh".
      2. The function f(N) defines an upper bound on the growth rate of the algorithm timing function.
      3. For example, if the time it takes an algorithm to run is linearly proportional to the problem size, then f(N) = N, and we say that the algorithm is O(N), or linear.
      4. In contrast, if the time it takes an algorithm to run is proportional to the square of the problem size, then f(N) = N², and we say that the algorithm is O(N²), or quadratic.
   2. Similarly, the "Omega" notation W(g(N)) is a lower bound on how much time an algorithm takes.
   3. The "theta" notation Q(h(N)) is an exact bound on how much time an algorithm takes.
   4. Finally, the "little-Oh" notation o(f(N)) is a strict upper bound on how much time an algorithm takes and
      the "little-omega" notation w(f(N)) is a strict lower bound on how much time an algorithm takes.

1. The variable N used in all of the notations refers to the size of the problem an algorithm is designed to solve.
2. Almost always in what we'll study, N is the size of the data structure the algorithm works with.
3. For example, if an algorithm adds the N elements of an array in a time that is linearly proportional to N, then the algorithm is O(N).
4. If an algorithm takes time proportional to N² to sort an N-element array, the algorithm is O(N²).

Function	Name	Goodness
O(c) or O(1)	Constant	Best
O(log N)	Logarithmic	Very good
O(log2 N) or O(log log N)	Log-squared	Very good
O(N)	Linear	Generally good
O(N log N)		Decent, particularly for sorting
O(N2)	Quadratic	OK, but we'd prefer something better
O(N3)	Cubic	Ditto
O(Nk)	Polynomial	Not so good, but we can live with it if we have to
O(2N), O(XN), O(N!)	Exponential	Bad news

1. Most frequently when we measure algorithm running times, we are concerned with the worst case performance.
   1. We care about this because we want to know how bad things can possibly get for all possible inputs to an algorithm.
   2. In general, when a big-Oh bound is given for an algorithm, it means the worst case behavior, unless specifically noted otherwise.
2. Average-case performance is also frequently of interest, since it measures the typical or regular behavior of an algorithm.
   1. Average case performance is of particular interest for certain algorithms where the worst-case behavior is very rare, or can be isolated to known data configurations.
   2. Unfortunately, average case analysis is often considerably more difficult to produce than worst case analysis.
3. Best-case is only occasionally of interest.

1. As we have been discussing, we are concerned overall with the broad measure of algorithm performance, not low-level coding details.
2. Hence, when calculating an algorithm timing function, we will make some general assumptions about how long it takes to execute specific elements of an algorithm.
3. First off, individual expression operations are all assumed to take some constant amount of time.
   1. For example, assignment statements, arithmetic operations, and relational comparisons are all constant-time.
   2. Even though it may take longer to add two numbers than to compare them, we don't really care because the time for both operations is constant.
4. The time to execute an if-statement is the constant time needed to evaluate its test, plus the maximum of the times for its if-clause and else-clause.
5. The running time for loops is generally where the O(f(N)) time is consumed.
   1. The mechanics of the loop involve some constant time for the initialization, test, and increment expressions.
   2. It's the body of the loop that is executed repetitively where the O(N) behavior occurs.
   3. Specifically, any loop that executes N times, is O(N).
   4. E.g.,

      for (i = 0; i < N; i++) { ... }
      

      is O(N), assuming that the body does not break out of the loop.
6. Nested loops are O(N²), e.g.,

   for (i = 0; i < N; i++) {
       for (j = 0; j < N; i++) { ... }
   }
   

   is O(N²); (think about why this is the case).
7. Consecutive statements are the sum of their individual running times.
   1. Since we're dealing with orders of magnitude, the running time of multiple consecutive assignment statements may be a large constant value when they're all summed up, but it's still just a constant value; i.e., O(3C) = O(100C) = O(C).
   2. Consecutive statements of larger orders of magnitude always dominate the running time, e.g.,

      for (i = 0; i < N; i++) { ... }
      for (i = 0; i < N; i++) { ... }
      for (i = 0; i < N; i++) {
          for (j = 0; j < N; i++) { ... }
      }
      

      is O(N²) overall, since O(N) + O(N) + O(N²) = O(N²)
8. The running time for recursive algorithms will generally take individual analysis.
   1. In a simple case such as the sumArray algorithm above, the recursion is performing the same form of computation as a for-loop, so it's O(N).
   2. We will see cases later in the quarter where recursive "divide and conquer" algorithms run in logarithmic time.

1. Consider the following algorithm that performs a simple linear search through an array:

   /**
    * Return the position in the given numbers array of the first occurrence of
    * the given numeric value.  Return -1 if the element is not in the array
    * or if the array is null.
    */
   public int searchArray(int[] numbers, int value) {
   
       int i;                                      // Array index
   
       /*
        * Return -1 if the array is null.
        */
       if (numbers == null) {
           return -1;
       }
   
       /*
        * Loop through the array, comparing the input value with each
        * element.  Return the index of the first element that equals the
        * value, if any.
        */
       for (i = 0; i < numbers.length; i++) {
           if (numbers[i] == value) {
               return i;
           }
       }
       return -1;
   }
   

2. As outlined above, N here is the length of the numbers array.
3. The best case for this search is O(c).
   1. In the best case we get lucky, when what we're searching for is the first element of the array.
   2. In this case we only execute one iteration of the loop, and all other computations take constant time.
   3. Hence, the overall performance is O(c), or we might even say O(1) since we do exactly one iteration of the loop.
4. The worst case for the search is O(N).
   1. This is the case where we're unlucky, and what we're searching for is all the way at the end, or not there at all.
   2. In this case we must execute all N loop iterations, which makes the running time O(N).
5. The average case is also O(N), but requires more analysis than the other cases.
   1. First we must make some assumptions about order of the array elements in the average case.
   2. If we assume that elements are in random order in the array, than statistical analysis says that each element is equally likely to occur at any give array position.
   3. Thus on average, if we search the array N times, we'll end up searching each position once.
   4. Given this, we can define the average running time in terms of the number of loop iterations as follows:

      (1 + 2 + 3 + ... + N) / N
      

      which equals

      S i / N
      
      i=1 to N
      
      

   5. If we recall that the closed-form formula for the summation is (N (N+1)) / 2, then we have the average time as ((N (N+1)) / 2) / N, which is (N + 1) / 2, which is O(N).
   6. To be entirely rigorous, we should in fact prove the closed form, i.e., that

      
      N
      
      S i = (N (N+1)) / 2
      
      i=1
      

   7. This can be done by the following inductive proof :
      1. The base case for N = 1 is

         
         1
         
         S i = (1 (1+1)) / 2
         
         i=1
         

         which reduces to 1 = 1.
         
         
      2. For the inductive step, we assume

         
         N
         
         S i = (N (N+1)) / 2
         
         i=1
         

         and prove

         
         N+1
         
         S i = ((N+1) (N+1+1)) / 2
         
         i=1
         

         Working from the summation side of the equation, we have

         
         N
         
         S i + N+1 , by the definition of summation
         
         i=1
         

         = (N (N+1)) / 2 + N + 1 , by the inductive hypothesis
         = (N (N+1)) / 2 + 2N/2 + 2/2 , by the identity rule
         = (N (N+1) + 2N + 2) / 2 , by common denominator
         = (N² + N + 2N + 2) / 2 , by distributive rule
         = (N² + 3N + 2) / 2 , by term addition
         = ((N + 1) (N + 2)) / 2 , by factoring
         q.e.d.
   8. The point of all of this is to demonstrate that average case analysis can be, and often is, non-trivial.

1. All of the timing analysis so far discussed has been analytic; that is, we have discussed general formulas for computing how long an algorithm runs.
2. To confirm such theoretical analysis, we generally want to code up the algorithm and get some actual, i.e., empirical, running times.
3. Example :

   import java.io.InputStreamReader;
   import java.io.IOException;
   import java.io.BufferedReader;
   
   public class TestprobRelPrime
   {
       public static void main( String [ ] args )
       {
           BufferedReader in = new BufferedReader( new
                                InputStreamReader( System.in ) );
           int x;
           String oneLine;
   
           System.out.println( "Enter an integer: " );
           try
           {
               oneLine = in.readLine( );
               x = Integer.parseInt( oneLine );
               long start = System.currentTimeMillis() ;
               double prob = probRelPrime(x) ;
               long end = System.currentTimeMillis() ;
   
               System.out.println( "The probability of two numbers less than " + x + " are relative prime is  " + prob );
                System.out.println("The running time = " + (end - start) + " miliseconds") ;
           }
           catch( IOException e )
             { System.out.println( e ); }
           catch( NumberFormatException e )
             { System.out.println( e ); }
       }
   
   
     public static int gcd( int m, int n )
           {
                if ( m < n ) return gcd(n,m) ;
                if ( n == 0 ) return m ;
                 if ( n == 1 ) return 1 ;
                
                  return gcd(n, m%n) ;
           }
   
   
   
      public static double probRelPrime(long n)
     {
       int rel = 0 , tot = 0 ;
     
        for ( int i  = 1 ; i  <= n ; i++ )
            for ( int j = i+1 ; j <= n ; j++ ) {
                 tot++ ;
                 if ( gcd(i,j) == 1 )   rel++ ;
            }
        return (double) rel / tot ;
     }
   }
   

1. Cubic maximum contiguous subsequence sum algorithm.

       static private int seqStart = 0;
       static private int seqEnd = -1;
       public static int maxSubSum1( int [ ] a )
       {
           int maxSum = 0;
   
           for( int i = 0; i < a.length; i++ )
               for( int j = i; j < a.length; j++ )
               {
                   int thisSum = 0;
   
                   for( int k = i; k <= j; k++ )
                       thisSum += a[ k ];
   
                   if( thisSum > maxSum )
                   {
                       maxSum   = thisSum;
                       seqStart = i;
                       seqEnd   = j;
                   }
               }
   
           return maxSum;
       }
   

2. Quadratic maximum contiguous subsequence sum algorithm.

       public static int maxSubSum2( int [ ] a )
       {
           int maxSum = 0;
   
           for( int i = 0; i < a.length; i++ )
           {
               int thisSum = 0;
               for( int j = i; j < a.length; j++ )
               {
                   thisSum += a[ j ];
   
                   if( thisSum > maxSum )
                   {
                       maxSum = thisSum;
                       seqStart = i;
                       seqEnd   = j;
                   }
               }
           }
   
           return maxSum;
       }
   

3. Linear-time maximum contiguous subsequence sum algorithm.

       public static int maxSubSum3( int [ ] a )
       {
           int maxSum = 0;
           int thisSum = 0;
   
           for( int i = 0, j = 0; j < a.length; j++ )
           {
               thisSum += a[ j ];
   
               if( thisSum > maxSum )
               {
                   maxSum = thisSum;
                   seqStart = i;
                   seqEnd   = j;
               }
               else if( thisSum < 0 )
               {
                   i = j + 1;
                   thisSum = 0;
               }
           }
   
           return maxSum;
       }
   

4. Recursive maximum contiguous subsequence sum algorithm.

       /**
        * Finds maximum sum in subarray spanning a[left..right].
        * Does not attempt to maintain actual best sequence.
        */
       private static int maxSumRec( int [ ] a, int left, int right )
       {
           int maxLeftBorderSum = 0, maxRightBorderSum = 0;
           int leftBorderSum = 0, rightBorderSum = 0;
           int center = ( left + right ) / 2;
   
           if( left == right )  // Base case
               return a[ left ] > 0 ? a[ left ] : 0;
   
           int maxLeftSum  = maxSumRec( a, left, center );
           int maxRightSum = maxSumRec( a, center + 1, right );
   
           for( int i = center; i >= left; i-- )
           {
               leftBorderSum += a[ i ];
               if( leftBorderSum > maxLeftBorderSum )
                   maxLeftBorderSum = leftBorderSum;
           }
   
           for( int i = center + 1; i <= right; i++ )
           {
               rightBorderSum += a[ i ];
               if( rightBorderSum > maxRightBorderSum )
                   maxRightBorderSum = rightBorderSum;
           }
   
           return max3( maxLeftSum, maxRightSum,
                        maxLeftBorderSum + maxRightBorderSum );
       }
   
       /**
        * Return maximum of three integers.
        */
       private static int max3( int a, int b, int c )
       {
           return a > b ? a > c ? a : c : b > c ? b : c;
       }
   

// an efficient exponentiation computation algorithm
public class Fig02_11
{
        public static boolean isEven( int n )
        {
            return n % 2 == 0;
        }

/* START: Fig02_11.txt*/
        public static long pow( long x, int n )
        {
/* 1*/      if( n == 0 )
/* 2*/          return 1;
/* 3*/      if( n == 1 )
/* 4*/          return x;
/* 5*/      if( isEven( n ) )
/* 6*/          return pow( x * x, n / 2 );
            else
/* 7*/          return pow( x * x, n / 2 ) * x;
        }
/* END */

        // Test program
        public static void main( String [ ] args )
        {
            System.out.println( "2^21 = " + pow( 2, 21 ) );
            System.out.println( "2^50 = " + pow( 2, 50 ) );
        }
    }

Example : The number of multiplications required in the computation of X⁶²

1. simple-mind, straight-forward algorithms, using for loop iteration : 61
2. Use the "efficient" algorithm given above : 9
3. It can be shown that it can be achieved by using only 8 multiplcations. (Homework)