Standard Analysis Techniques

• Constant time statements
• Analyzing Loops
• Analyzing Nested Loops
• Analyzing Sequence of Statements
• Analyzing Conditional Statements

Constant time statements

• Simplest case: O(1) time statements
• Assignment statements of simple data types
  int x = y;
• Arithmetic operations:
  x = 5 * y + 4 – z;
• Array referencing:
  A[j] = 5;
• Array assignment:
  ” j, A[j] = 5;
• Most conditional tests:
  if (x < 12) …

Analyzing Loops[1]

• Any loop has two parts:
• How many iterations are performed?
• How many steps per iteration?

    int sum = 0,j;

    for (j=0; j < N; j++)

      sum = sum +j;

• Loop executes N times (0..N-1)
• 4 = O(1) steps per iteration
• Total time is N * O(1) = O(N*1) = O(N)

Analyzing Loops[2]

• What about this for loop?

    int sum =0, j;

    for (j=0; j < 100; j++)

       sum = sum +j;

• Loop executes 100 times
• 4 = O(1) steps per iteration
• Total time is 100 * O(1) = O(100 * 1) = O(100) = O(1)

Analyzing Nested Loops[1]

• Treat just like a single loop and evaluate each level of nesting as needed:

int j,k;

   for (j=0; j<N; j++)

      for (k=N; k>0; k–)

         sum += k+j;

• Start with outer loop:
• How many iterations? N
• How much time per iteration? Need to evaluate inner loop
• Inner loop uses O(N) time
• Total time is N * O(N) = O(N*N) = O(N2)

Analyzing Nested Loops[2]

• What if the number of iterations of one loop depends on the counter of the other?

    int j,k;

      for (j=0; j < N; j++)

         for (k=0; k < j; k++)

            sum += k+j;

• Analyze inner and outer loop together:
• Number of iterations of the inner loop is:
• 0 + 1 + 2 + … + (N-1) = O(N2)

Analyzing Sequence of Statements

• For a sequence of statements, compute their complexity functions individually and add them up

 for (j=0; j < N; j++)

for (k =0; k < j; k++)

sum = sum + j*k;          O(N2)

for (l=0; l < N; l++)

sum = sum -l;               O(N)

cout<<“Sum=”<<sum;   O(1)

Total cost is O(N2) + O(N) +O(1) = O(N2)

SUM RULE

Analyzing Conditional Statements

What about conditional statements such as

 if (condition)

      statement1;

   else

      statement2;

where statement1 runs in O(N) time and statement2 runs in O(N2) time?

We use “worst case” complexity: among all inputs of size N, that is the maximum running time?

The analysis for the example above is O(N2)

Best Case

• Best case is defined as which input of size n is cheapest among all inputs of size n.
• “The best case for my algorithm is n=1 because that is the fastest.” WRONG!