A Simple Example of Run-time Complexity#

Suppose that we want to print a carat ‘^’ of varying dimensions out of asterisks, with the number of rows to print stored in the variable size. For example, if size is 5, then we want to print:

          *
        *   *
      *       *
    *           *
  *               *

We have already written a Java method to print a given number of characters to standard output, see Chapter 1 Practice Questions, namely:

/**
 * Prints aChar the given number of times to standard output.  No
 * newline is added.
 *
 * @param num - the number of times to print the char
 * @param aChar - the char to print
 */
public static void printNumChars(int num, char aChar){
   while (num > 0){
      System.out.print(aChar);
      num = num - 1;
   }
}

We want to use that method in our new code.

Two Programs#

The following two pieces of Java code, each prints a correct carat of a variable size, assuming that size is bigger than 0:

Program 1

Program 2

 
int rowNum = 0;
int frontBlanks = 2 * size;
int middleBlanks = -1;
while (rowNum < size){
   if (rowNum == 0){
      printNumChars(frontBlanks, ' ');
      System.out.println('*');
   }
   else{
      printNumChars(frontBlanks, ' ');
      System.out.print('*');              
      printNumChars(middleBlanks, ' ');
      System.out.print('*');
      System.out.println();                
   }
   frontBlanks = frontBlanks - 2;
   middleBlanks = middleBlanks + 4;
   rowNum = rowNum + 1;
}//while

int rowNum = 1;
int frontBlanks = 2 * size;
    
printNumChars(frontBlanks, ' ');
System.out.println('*');
    
frontBlanks = frontBlanks - 2;        
int middleBlanks = 3;
while (rowNum < size) {
   printNumChars(frontBlanks, ' ');
   System.out.print('*');
   printNumChars(middleBlanks, ' ');
   System.out.print('*');
   System.out.println();

   frontBlanks = frontBlanks - 2;
   middleBlanks = middleBlanks + 4;
   rowNum = rowNum + 1;
}//while

The biggest difference in the two programs is that Program 1 puts the printing of all of the rows into the loop while Program 2 only puts the printing of rows 2 and onward into the loop. Thus, Program 1 needs a special case to deal with the first row of the carat within the loop, where there is only a single asterisk. Program 2 deals with the special case outside of the loop. The code for both programs is about the same length. Which program is better?

Complexity of the Two Programs#

To find the complexity of each program, we could count every single operation that is done. This is a lot of work and it is more usual to focus on the most expensive operations and count those. In these programs, those expensive operations could be the comparisons: rowNum < size and rowNum == 0. Let’s count those operations when size is 5.

Value of rowNum

Program 1 Comparison Operations

Program 2 Comparison Operations

0

2

1

2

1

2

2

1

3

2

1

4

2

1

5

1

1

Total

11

5

If you change size to 6, you will find that Program 1 does 13 comparisons while Program 2 does 6. If size is 9, then Program 1 does 19 comparisons while Program 2 does 9 comparisons. Program 1 always does more work than Program 2, so Program 1 will always run slower, on any computer, than Program 2 will. It doesn’t matter if you find the fastest computer on earth, Program 1 will be slower. We say that Program 2 is better, more efficient at run-time.

We can build a model for the run-time complexities as a function of \(n\), where \(n\) corresponds to size. In general, the run-time complexity of Program 1 is

\[ 2n + 1 \]

and the run-time complexity of Program 2 is

\[ n. \]

While Program 1 runs slower than Program 2, the amount of difference is not huge – it is only twice as slow. Both programs run in linear time, which we characterize using order notation as \(θ(n)\). If we say this out loud, it would be “theta of \(n\)” and it means the complexity is a linear function of some sort.