18.3. Example Problems

1. Example 1

   Here is an algorithm that solves the problem of printing all elements of an array.

   void printA(int[] a) {
       for(int i = 0; i < a.length; i++) {
           System.out.println(a[i]);
       } // for
   } // printA
   

   Questions:

   • What is the problem size?

   • What is T(n) if the set of key processing steps only includes print-like statements? Note: We choose print statements as our key processing step because they take significantly longer to execute when compared to the other operations in this method (addition, assignment, array access, etc.).

   Think about the answers to the previous two questions before reading ahead

   Towards a Sample Solution:

   • What is the problem size? In this example, the problem size is the array length. We know this because the number of operations that will execute is determined by the length of the array. If we increase the size of a, that directly impacts the number of print statements that will execute. Therefore, let n = a.length.

   • What is T(n) if the set of key processing steps only includes print-like statements?

     You could try to find a pattern by performing multiple executions of the program with different array lengths and recording the number of print-like statements:

     n = a.length	# print-like statements
     0	0
     1	1
     2	2
     ...	...
     4	4
     ...	...
     8	8
     ...	...
     16	16
     ...	...

     After multiple executions, we think we see a pattern: T(n) = n. Indeed, if we check this formula for each row in the table we made, then we’ll see that this formula works! However, this strategy of finding a pattern is often tedious and error-prone as the algorithms get more complicated. Instead, we prefer to use a more systematic approach that leads to fewer errors and gives us insight into the structure of the algorithm with respect to the key processing steps.

     NOTE: That being said, creating the table is a good way to verify your formula for T(n) after deriving it systematically.

     Now, to derive T(n) for this algorithm in a more systematic way, let’s first identify the most nested operation – here, operation refers to any instruction in the set of key processing steps:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) {
             System.out.println(a[i]); // -------> 1
         } // for
     } // printA
     

     Next, we identify the enclosing loop:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // -----\
             System.out.println(a[i]); // -------> 1 | n
         } // for // --------------------------------/
     } // printA
     

     Finally, we identify how many iterations the loop will have with respect to n:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // -----\
             System.out.println(a[i]); // -------> 1 | n
         } // for // --------------------------------/
     } // printA
     

     If you label the operations and iterations as we did in the diagram above, then you can simply multiply across in a simple scenario like this:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // -----\
             System.out.println(a[i]); // -------> 1 | n ⇒ T(n) = 1 * n
         } // for // --------------------------------/
     } // printA
     

     Therefore, T(n) = n for this printA method. You might read this as “The number of print statements this method performs is equal to the length of the array”.

2. Example 2:

   Here is an algorithm that solves the problem of printing all elements of an array in a square fashion:

   void printA(int[] a) {
       for(int i = 0; i < a.length; i++) {
           for(int j = 0; j < a.length; j++) {
               System.out.print(a[i] + " ");
           } // for
           System.out.println();
       } // for
   } // printA
   

   Questions:

   • What is the problem size?

   • What is T(n) if the set of key processing steps only includes print-like statements?

   Think about the answers to the previous two questions before reading ahead

   Towards a Sample Solution:

   • What is the problem size? In this example, the problem size is the array length. Therefore, let n = a.length.

   • What is T(n) if the set of key processing steps only includes print-like statements? To answer this question, let’s first identify the most nested operation:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) {
             for(int j = 0; j < a.length; j++) {
                 System.out.print(a[i] + " ");  // -------> 1
             } // for
             System.out.println();
         } // for
     } // printA
     

     Next, we identify the enclosing loop and its number of iterations:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) {
             for(int j = 0; j < a.length; j++) { // ----------\
                 System.out.print(a[i] + " ");  // -------> 1 | n
             } // for  // ------------------------------------/
             System.out.println();
         } // for
     } // printA
     

     It appears that there is another print-like statement at the same level as the loop we just identified:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) {
             for(int j = 0; j < a.length; j++) { // ----------\
                 System.out.print(a[i] + " ");  // -------> 1 | n
             } // for  // ------------------------------------/
             System.out.println(); // ------------------------> 1
         } // for
     } // printA
     

     Now, we identify the next enclosing loop and its number of iterations:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // ------------------\
             for(int j = 0; j < a.length; j++) { // ----------\   |
                 System.out.print(a[i] + " ");  // -------> 1 | n | n
             } // for  // ------------------------------------/   |
             System.out.println(); // ------------------------> 1 |
         } // for ------------------------------------------------/
     } // printA
     

     If you label the operations and iterations as we did in the diagram above, then you can simply multiply across and add up the results in a scenario like this:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // ------------------\
             for(int j = 0; j < a.length; j++) { // ----------\   |
                 System.out.print(a[i] + " ");  // -------> 1 | n | n ⇒ T(n) = 1 * n * n
             } // for  // ------------------------------------/   |
             System.out.println(); // ------------------------> 1 |           +     1 * n
         } // for ------------------------------------------------/
     } // printA
     

     Therefore, T(n) = n^2 + n for this particular printA method.

3. Example 3 [Tricky]:

   Here is a modified version of the previous example:

   void printA(int[] a) {
       for(int i = 0; i < a.length; i++) {
           for(int j = 0; j < 10; j++) {
               System.out.print(a[i] + " ");
           } // for
           System.out.println();
       } // for
   } // printA
   

   Questions:

   • What is the problem size?

   • What is T(n) if the set of key processing steps only includes print-like statements?

   Think about the answers to the previous two questions before reading ahead

   Towards a Sample Solution:

   • What is the problem size? In this example, the problem size is the array length. Therefore, let n = a.length.

   • What is T(n) if the set of key processing steps only includes print-like statements? To answer this question, let’s diagram the code the way we did in the previous examples:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // -------------------\
             for(int j = 0; j < 10; j++) { // ----------------\    |
                 System.out.print(a[i] + " ");  // -------> 1 | 10 | n
             } // for  // ------------------------------------/    |
             System.out.println(); // ------------------------> 1  |
         } // for -------------------------------------------------/
     } // printA
     

     This was the tricky part. The inner for-loop only iterates 10 times. This changes the overall timing function. Just as before, you can simply multiply across and add up the results:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // -------------------\
             for(int j = 0; j < 10; j++) { // ----------------\    |
                 System.out.print(a[i] + " ");  // -------> 1 | 10 | n ⇒ T(n) = 1 * 10 * n
             } // for  // ------------------------------------/    |
             System.out.println(); // ------------------------> 1  |           +      1 * n
         } // for -------------------------------------------------/
     } // printA
     

     Therefore, T(n) = 11n for this particular printA method!

     Note: One brutally common mistake is to assume that the number of the resulting polynomial always increases with the number of loop nestings. This is not the case, as is illustrated in the last example. Even though there are two loops that are nested, the overall degree of the polynomial is 1 and not 2.

4. Example 4 [Trickier]:

   Here is a slightly modified version of the previous example (pay close attention to spot the subtle differences):

   void printA(int[] a) {
       for(int i = 0; i < a.length; i++) {
           for(int j = 0; j < i; j++) {
               System.out.print(a[i] + " ");
           } // for
           System.out.println();
       } // for
   } // printA
   

   Questions:

   • What is the problem size?

   • What is T(n) if the set of key processing steps only includes print-like statements?

   Think about the answers to the previous two questions before reading ahead

   Towards a Sample Solution:

   • What is the problem size? In this example, the problem size is the array length. Therefore, let n = a.length.

   • What is T(n) if the set of key processing steps only includes print-like statements? To answer this question, let’s diagram the code the way we did in the previous examples:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // --------------------\
             for(int j = 0; j < i; j++) { // -----------------\     |
                 System.out.print(a[i] + " ");  // -------> 1 | < n | n
             } // for  // ------------------------------------/     |
             System.out.println(); // ------------------------> 1   |
         } // for --------------------------------------------------/
     } // printA
     

     This was the tricky part. The inner for-loop may have as many as n - 1 iterations, however, this number changes based on what iteration of the outermost loop the code is in. We don’t want to mark the loop as having the minimum number since that would undercount, however, it’s okay in this scenario to mark it with the maximum number (technically an overcount) so long as we indicate it’s < that number. Just as before, you can simply multiply across and add up the results, this time accounting for the presence of < instead of an =:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // --------------------\
             for(int j = 0; j < i; j++) { // -----------------\     |
                 System.out.print(a[i] + " ");  // -------> 1 | < n | n ⇒ T(n) < 1 * n * n
             } // for  // ------------------------------------/     |
             System.out.println(); // ------------------------> 1   |           +     1 * n
         } // for --------------------------------------------------/
     } // printA
     

     Therefore, T(n) < n^2 + n for this particular printA method!

5. Example 5 [Even Trickier]:

   Below is a slightly modified version of the previous example, now decomposed into two separate methods.

   void printUntil(int[] a, int i) {
       for(int j = 0; j < i; j++) {
           System.out.print(a[i] + " ");
       } // for
   } // printUntil
   

   void printA(int[] a) {
       for(int i = 0; i < a.length; i++) {
           printUntil(a, i);
           System.out.println();
       } // for
   } // printA
   

   Here, we will focus our analysis on the algorithm described by printA. Since this example has the same code as the previous example, albeit split between two methods, our analysis should result in the same timing function.

   Questions:

   • What is the problem size?

   • What is T(n) if the set of key processing steps only includes print-like statements?

   Think about the answers to the previous two questions before reading ahead

   Towards a Sample Solution:

   • What is the problem size? In this example, we actually have two problem sizes!

     • The problem size for printA is the array length because increasing or decreasing that length impacts how long the method takes to execute. Therefore, let n = a.length when discussing this method.

     • The problem size for printUntil is its parameter i. Although we are passing the array into the method, the array’s length does not impact how long this method takes to execute; however, it’s parameter i does. Therefore, let n = i when discussing this method.

   • Before we continue, please remember that n (the problem size) means something different depending on the method that we’re analyzing.

   • First, let’s analyze printUntil to derive its timing function. So that we don’t confuse the function we derive for this method with the one we’ll derive for printA, let U(n) denote for this method where n = i. What is U(n) if the set of key processing steps only includes print-like statements? To answer this question, let’s diagram the code the way we did in the previous examples:

     void printUntil(int[] a, int i) {
         for(int j = 0; j < i; j++) { // -------------------\
             System.out.print(a[i] + " "); // ----------> 1 | = i ⇒ U(n) = 1 * i
         } // for // ---------------------------------------/             = 1 * n [since n = i]
     } // printUntil                                                      = n
     

   • As we can see, U(n) = n print-like statements for printUntil where n = i. Remember that the problem size n for printUntil is different than the problem size for printA.

   • Now that we have derived the timing function for our helper method, let’s analyze the printA method. What is T(n) if the set of key processing steps only includes print-like statements? Remember that the problem size n for printA is different than the problem size for printUntil. To answer this question, let’s diagram the code the way we did in the previous examples:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // ----------------\
             printUntil(a, i);     // -------------------> U(i) | n [where n = a.length]
             System.out.println(); // -------------------> 1    |
         } // for // -------------------------------------------/
     } // printA
     

     Before we continue, we note that U(i) here is the U(n) function that we previously derived for printUntil called to explicitly supply i as its n value. This is called function composition.

     Since printA utilizes printUntil, it stands to reason that T(n) needs to utilize U(n):

   • To complete this tricky derivation, we now use the result of the function composition to replace U(n) with its result:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // ---------------\
             printUntil(a, i);     // -------------------> i   | n [since U(i) = i]
             System.out.println(); // -------------------> 1   |
         } // for // ------------------------------------------/
     } // printA
     

     We want out final derivation to be in terms of n. Within the observed loop, we see that printUntil(a, i) will execute 1 * i print-like statements. We further observe that the largest value that i can be inside its enclosed loop is n. Therefore, we simplify the expression in order to provide a reasonable upper bound with respect to n, then complete the derivation:

     void printA(int[] a) {
         for(int i = 0; i < a.length; i++) { // ---------------\
             printUntil(a, i);     // -------------------> < n | n ⇒ T(n) < n * n
             System.out.println(); // -------------------> 1   |           + 1 * n
         } // for // ------------------------------------------/
     } // printA
     

     Therefore, T(n) < n^2 + n for this particular printA method! This should not be surprising as this is the same algorithm from Example 4 decomposed into two separate methods.

6. Example 6 [Even Trickier 2]:

   Here is an algorithm that solves the problem of printing characters of a string, in reverse, cutting the index value by 3 each time.

   void printS(String s) {
       for(int i = s.length() - 1; i > 0; i = i / 3) {
           System.out.println(s.charAt(i));
       } // for
   } // printS
   

   Questions:

   • What is the problem size?

   • What is T(n) if the set of key processing steps only includes print-like statements?

   Think about the answers to the previous two questions before reading ahead

   Towards a Sample Solution:

   • What is the problem size? In this example, the problem size is the string length. Therefore, let n = s.length().

   • What is T(n) if the set of key processing steps only includes print-like statements? If we follow our established strategy for a derivation, we might end up with the following diagram:

     void printS(String s) {
         for(int i = s.length() - 1; i > 0; i = i / 3) { // --\
             System.out.println(s.charAt(i)); // ---------> 1 | < n ⇒ T(n) < 1 * n
         } // for // -----------------------------------------/
     } // printS
     

     While this is correct, it is not the best estimate for an upper bound that we can derive for the number of iterations of the observed loop. To get a better estimate, we first observe that this loop behaves a little differently than the loops we’ve observed in the previous examples – instead of incrementing or decrementing by some fixed value, the loop variable instead decreases by multiplying or dividing by some fixed value. In this case, the loop variable i is divided by 3 after each iteration. We can use this to our advantage to derive a better estimate.

     Without loss of generality, assume that n = s.length() is a power of 3. To determine how many iterations of the loop occur, we might ask the following question:

     If you start with n - 1, how many times can you integer divide by 3 before you get to 0?

     This can be slightly reworded to:

     If you start with n, how many times can you integer divide by 3 until the value is 1?

     If we let k denote the number of iterations of the loop, then we have the following:

     void printS(String s) {
         for(int i = s.length() - 1; i > 0; i = i / 3) { // --\
             System.out.println(s.charAt(i)); // ---------> 1 | k
         } // for // -----------------------------------------/
     } // printS
     

     This can be modeled as a math problem:

     n / 3^k = 1
     

     To answer the question “how many times can you integer divide”, we need only solve for k using some precalculus magic (i.e., logarithms):

     1. Original model:

        n / 3^k = 1
        

     2. Multiply both sides by 3^k:

        3^k = n
        

     3. Take the logarithm of both sides:

        log(3^k) = log(n)
        

     4. Move the exponent out of the logarithm:

        k * log(3) = log(n)
        

     5. Divide both sides by log(3):

        k = log(n) / log(3)
        

     6. Assuming both logarithms are the same base (they are), dividing the first logarithm by log(3) changes the base of the logarithm to 3:

        k = log3(n)
        

        where log3(n) denotes the base-3 logarithm of n.

     We did make a pretty big assumption that n is a power of 3. If n is not a power of 3, then the base-3 logarithm will not be in an integer – this poses a problem as the count for the number of iterations must be an integer. We could get fancy and use the ceil (ceiling function) to get an exact answer:

     k = ceil(log3(n))
     

     However, this will make formally establishing a complexity class (covered later) a little trickier. Instead, we’ll let k denote an upper bound instead of an equality – that is, we’ll express it as some value (assumed to be an integer) less than or equal to the logarithm plus one:

     k ≤ log3(n) + 1
     

     This is okay since ceil(log3(n)) ≤ log3(n) + 1 for all reasonable n values. In a Discrete Mathematics course, you would need to be more rigorous about this. For now, we’ll take it as a reasonable estimate. Now that we have a value for k, we can substitute it into our derivation:

     void printS(String s) {
         for(int i = s.length() - 1; i > 0; i = i / 3) { // --\
             System.out.println(s.charAt(i)); // ---------> 1 | ≤ log3(n) + 1 ⇒ T(n) ≤ 1 * log3(n) + 1
         } // for // -----------------------------------------/
     } // printS
     

     Therefore, T(n) ≤ log3(n) + 1 for this particular printS method! Taking advantage of the way the loop iterates differently (i.e., multiply/dividing vs. adding/subtracting) leads us to a much better estimate of the number of key processing steps with respect to the problem size.