COMPUTING SCIENCE 210
Algorithm Analysis and Data Structures

Review Questions — Algorithm Analysis

1. Order the following list of functions by their asymptotic growth, such that if function f(n) is above or to the left of g(n), then f(n) = O(g(n)) (i.e., put them in order, fastest to slowest.)

   1. n
   2. 2ⁿ
   3. n ⁿ
   4. log n
   5. n ³ - 5n
   6. n² + log n
   7. n !
   8. n log n

2. Characterize the following summations (exactly) in terms of n:

   1. Sigma _{1 <= i <= n} ( 3i + 4 ) [where Sigma is the summation symbol].

3. Give a Big-Oh characterization, in terms of n, of the running time of each of the following Java methods.

   1.         public void ExA( int n ) {
                  int a;
                  for ( int i = 0; i < n; i += 2 )
                      a = i;
              }

   2.         public void ExB( int n ) {
                  int a;
                  for ( int i = 0; i < n * n; i++ )
                      a = i;
              }