Example 5.6.1

We begin with an analysis of a simple assignment to an integer variable.

a = b;

a = b;

Because the assignment statement takes constant time, it is \(\Theta(1)\).

Example 5.6.2

Consider a simple for loop.

sum = 0;
for (i=1; i<=n; i++) {
   sum += n;
}

sum = 0;
for (i=1; i<=n; i++)
   sum += n;

The first line is \(\Theta(1)\). The for loop is repeated \(n\) times. The third line takes constant time so, by simplifying rule (4), the total cost for executing the two lines making up the for loop is \(\Theta(n)\). By rule (3), the cost of the entire code fragment is also \(\Theta(n)\).

Example 5.6.3

We now analyze a code fragment with several for loops, some of which are nested.

sum = 0;
for (j=1; j<=n; j++) {     // First for loop
  for (i=1; i<=j; i++) {  //   is a double loop
    sum++;
  }
}
for (k=0; k<n; k++) {      // Second for loop
   A[k] = k;
}

sum = 0;
for (j=1; j<=n; j++)     // First for loop
   for (i=1; i<=j; i++)  //   is a double loop
      sum++;
for (k=0; k<n; k++)      // Second for loop
   A[k] = k;

This code fragment has three separate statements: the first assignment statement and the two for loops. Again the assignment statement takes constant time; call it \(c_1\). The second for loop is just like the one in Example 5.6.2 and takes \(c_2 n = \Theta(n)\) time.

The first for loop is a double loop and requires a special technique. We work from the inside of the loop outward. The expression sum++ requires constant time; call it \(c_3\). Because the inner for loop is executed \(j\) times, by simplifying rule (4) it has cost \(c_3j\). The outer for loop is executed \(n\) times, but each time the cost of the inner loop is different because it costs \(c_3j\) with \(j\) changing each time. You should see that for the first execution of the outer loop, \(j\) is 1. For the second execution of the outer loop, \(j\) is 2. Each time through the outer loop, \(j\) becomes one greater, until the last time through the loop when \(j = n\). Thus, the total cost of the loop is \(c_3\) times the sum of the integers 1 through \(n\). We know that

which is \(\Theta(n^2)\). By simplifying rule (3), \(\Theta(c_1 + c_2 n + c_3 n^2)\) is simply \(\Theta(n^2)\).

Example 5.6.4

Compare the asymptotic analysis for the following two code fragments.

sum1 = 0;
for (i=1; i<=n; i++) {     // First double loop
  for (j=1; j<=n; j++) {  //   do n times
    sum1++;
  }
}

sum2 = 0;
for (i=1; i<=n; i++) {     // Second double loop
  for (j=1; j<=i; j++) {  //   do i times
    sum2++;
  }
}

sum1 = 0;
for (i=1; i<=n; i++)     // First double loop
   for (j=1; j<=n; j++)  //   do n times
      sum1++;

sum2 = 0;
for (i=1; i<=n; i++)     // Second double loop
   for (j=1; j<=i; j++)  //   do i times
      sum2++;

In the first double loop, the inner for loop always executes \(n\) times. Because the outer loop executes \(n\) times, it should be obvious that the statement sum1++ is executed precisely \(n^2\) times. The second loop is similar to the one analyzed in the previous example, with cost \(\sum_{j = 1}^{n} j\). This is approximately \({1 \over 2} n^2\). Thus, both double loops cost \(\Theta(n^2)\), though the second requires about half the time of the first.

Example 5.6.5

Not all doubly nested for loops are \(\Theta(n^2)\). The following pair of nested loops illustrates this fact.

sum1 = 0;
for (k=1; k<=n; k*=2) {    // Do log n times
  for (j=1; j<=n; j++) {  // Do n times
    sum1++;
  }
}

sum2 = 0;
for (k=1; k<=n; k*=2) {    // Do log n times
  for (j=1; j<=k; j++) {  // Do k times
    sum2++;
  }
}

sum1 = 0;
for (k=1; k<=n; k*=2)    // Do log n times
   for (j=1; j<=n; j++)  // Do n times
      sum1++;

sum2 = 0;
for (k=1; k<=n; k*=2)    // Do log n times
   for (j=1; j<=k; j++)  // Do k times
      sum2++;

When analyzing these two code fragments, we will assume that \(n\) is a power of two. The first code fragment has its outer for loop executed \(\log n+1\) times because on each iteration \(k\) is multiplied by two until it reaches \(n\). Because the inner loop always executes \(n\) times, the total cost for the first code fragment can be expressed as

So the cost of this first double loop is \(\Theta(n \log n)\). Note that a variable substitution takes place here to create the summation, with \(k = 2^i\).

In the second code fragment, the outer loop is also executed \(\log n+1\) times. The inner loop has cost \(k\), which doubles each time. The summation can be expressed as

where \(n\) is assumed to be a power of two and again \(k = 2^i\).