10. Program Execution Time

10.1 Introduction

One of the questions which computer scientists have dealt with from the very beginning of studies in this field has to do with the question just "How far can one go in computer science?", or "What are the limitations of computer science?" We have studied algorithms which are too time consuming to execute on any computer. However there are other kinds of questions we should ask. For example, there are problems for which there are no known, as of yet, algorithms. There are problems which are known to be non-computable. A problem is said to be non-computable if a proof exists that, given the current structure for computers or computation, no program can be written which solves the problem.

10.2 Order Notation

In Chapter 5, Algorithms, we developed the idea of quantifying the amount of work done during the execution of a program. This quantification involved defining what was meant by work and then presenting the work done as a function of the size of the problem. The idea of work done by a program may include the number of times a certain operation is performed or the amount of memory used by the program or the execution time of the program. Since any of these categories of work ultimately take some amount of time, we can simplify our analysis, without any loss of generality, by using execution time as our measure of program performance.

We say a computer program is order f n, written as O(f n), if there is a function f and a constant k such that the execution time of the program is not more than k * f n. We say that n is the size of the problem which the program solves and, of course, we are often interested in what happens to the execution time when the size of the problem is large.

As an example of the order notation consider the following function which computes the largest element of a non-empty list of numbers.

10.2.1 Maximum Function


maximum =: monad def 'max_helper (rest y.) ; head y.'

max_helper =: monad define
('ls' ; 'max') =. y.
if. nullp ls
    do. max
  elseif. max < head ls
    do. max_helper (rest ls) ; head ls
  elseif. 1
    do. max_helper (rest ls) ; max
end.
)

The traced version, traced_maximum, gives the following output:


traced_maximum =: monad def 'traced_max_helper (rest y.) ; head y.'

traced_max_helper =: monad define
entering y.
('ls' ; 'max') =. y.
if. nullp ls
    do. max
  elseif. max < head ls
    do. leaving traced_max_helper (rest ls) ; head ls
  elseif. 1
    do. leaving traced_max_helper (rest ls) ; max
end.
)

   traced_maximum 1 9 2 4 10 5 ==>
Entering, input =
+----------+-+
|9 2 4 10 5|1|
+----------+-+
Entering, input =
+--------+-+
|2 4 10 5|9|
+--------+-+
Entering, input =
+------+-+
|4 10 5|9|
+------+-+
Entering, input =
+----+-+
|10 5|9|
+----+-+
Entering, input =
+-+--+
|5|10|
+-+--+
Entering, input =
++--+
||10|
++--+
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
10

One can easily verify that the number of times max_helper is used, i.e., the execution time of maximum, is n, the number of elements in ls. Hence, the execution time of maximum is of order n.

10.2.2 A Sorting Algorithm

Suppose we which to sort a list of numbers such as (9 1 4 2) in ascending order. We could make a pass through the elements of this list using the following algorithm called a sort-pass. Compare the first two elements. Since they are not in sorted order, interchange them producing (1 9 4 2). Continue this process with the next two elements producing (1 4 9 2) and finally, compare the last two elements and since they are not in sorted order, interchange them producing (1 4 2 9). The sort-pass has succeeded in finding the largest element in the list and putting it in the last position.

10.2.3 sort_pass Function


sort_pass =: monad define
NB. stop when we have a list of two items
if. nullp rest rest y.
  do. if. (head y.) < head rest y.
        do. y.
        else. reverse y.
      end.
  else. one =. head y.
        two =. head rest y.
       if. one < two
         do. one append sort_pass rest y.
         else. two append sort_pass one append rest rest y.
       end.
end.
)

sort_pass 9 1 4 2 ==>
1 4 2 9

Next we use a traced version of sort_pass to study the execution of this function.


traced_sort_pass =: monad define
NB. stop when we have a list of two items
entering y.
if. nullp rest rest y.
  do. if. (head y.) < head rest y.
        do. leaving y.
        else. leaving reverse y.
      end.
  else. one =. head y.
        two =. head rest y.
       if. one < two
         do. leaving one append traced_sort_pass rest y.
         else. leaving two append traced_sort_pass one append rest rest y.
       end.
end.
)

   traced_sort_pass 9 1 4 2 ==>
Entering, input = 9 1 4 2
Entering, input = 9 4 2
Entering, input = 9 2
Leaving, result = 2 9
Leaving, result = 4 2 9
Leaving, result = 1 4 2 9
1 4 2 9

In the above trace of sort_pass with n = 4, it is clear that 3 comparisons were made. From this it follows that when a list has n elements, sort-pass makes n - 1 comparisons.

To complete the sort of a list, we notice that we could use sort_pass on the list which remains after removing the last (which is now known to be the largest) element. This process should be repeated on successively shorter lists until a list of two numbers is obtained.

10.2.4 sort Function


sort =: monad define
NB. stop when we have a list of two items
if. nullp rest rest y.
  do. sort_pass y.
  else. result =. sort_pass y.
        (sort drop_last result) append last result
end.
)

   sort 9 1 4 2 ==>
1 2 4 9

If we use the traced_sort, we have:


traced_sort =: monad define
NB. stop when we have a list of two items
entering y.
if. nullp rest rest y.
  do. leaving sort_pass y.
  else. result =. sort_pass y.
        leaving (traced_sort drop_last result) append last result
end.
)

   traced_sort 9 1 4 2 ==>
Entering, input = 9 1 4 2
Entering, input = 1 4 2
Entering, input = 1 2
Leaving, result = 1 2
Leaving, result = 1 2 4
Leaving, result = 1 2 4 9
1 2 4 9

This sort algorithm is referred to as bubble sort. The name is derived from the fact that as each pass is made, the largest element in a sub-list sinks all the way to the bottom of the list, displacing each smaller element one position, at most, upward. As the sort progresses, the larger elements sink quickly to their lower positions while the smaller elements slowly "bubble" up to their final resting place, one position per sort_pass.

We see that when n = 4, sort-pass is used 3 times, that is, sort_pass is used on the entire list 9 1 4 2 to find the largest element, 9, and put it at the end. Then sort_pass is used again on the list 1 4 2 to find its largest element, 4. Finally, sort_pass is used on 1 2 and that two element list is returned since the elements are in the right order. Next, we count the number of comparisons required to sort this 4 element list. The first sort_pass uses 3 comparisons, the second uses 2 comparisons and the last uses 1 comparison for a total of 6 comparisons.

For a list of n elements, the comparison total is:


c = (n - 1) + (n - 2) +...+ 2 + 1

We wish to simplify the formula for c. We can also write c as:


c = 1 + 2 +...+ (n - 2) + (n + 1)

Adding these two formulas we have


2 * c = n + n +...+ n + n = n * (n - 1)

so that


c = n * (n - 1) % 2) = (n * n % 2) - n % 2

Since c involves only terms of n squared and n, we say that the bubble sort algorithm is of order n². To sort a list of 1000 elements will require almost 500,000 comparisons while sorting a list 1,000,000 elements will require about 10¹² comparisons. This number is so large that bubble sorting lists of this size is not practical. There are faster sorting algorithms. Hoare's QuickSort algorithm runs in a time of order n * log₂ n.

The execution times for the maximum function, bubble sort and QuickSort are compared in the following chart.

The numeric data for this graph shows that the bubble sort is probably not practical for n values much larger than 1000 and it also shows that even QuickSort will have difficulty sorting large lists.

         1000         10000  100000        1000000       n                              
       499500      49995000  4999950000    5E+11         n * (n - 1) % 2                
   9965.78428    132877.124  1660964.05    19931568.6    n * log₂ n

10.2.5 Polynomial Execution Time

A polynomial in n of degree k is a function which can be written in the form:


a₀ + a₁*n¹ + a₂*n² +...+ a_k*n^k

where n is the size of the problem and the a_i 's are constants.

A computation is said to be tractable if its execution time is less than or equal to some polynomial in n. It follows that a computation is intractable if its execution time is greater than any polynomial.

10.3 Intractable Computation

Recall that the fibonacci function, studied in Chapter 5

10.3.1 fibonacci Function


fibonacci =. monad define
if. y. < 2
  do. y.
  else. (fibonacci y. - 1) + fibonacci y. - 2
end.
)

had an execution time of


e*qⁿ + f*rⁿ

for suitably chosen e, q,f and r.

We can verify the exponential behavior of the execution time of fibonacci experimentally. The rather complex J expression:

   (11 10 $ 'fibonacci ') ,. format 11 1 $ 15 + i. 11
fibonacci 15
fibonacci 16
fibonacci 17
fibonacci 18
fibonacci 19
fibonacci 20
fibonacci 21
fibonacci 22
fibonacci 23
fibonacci 24
fibonacci 25

can be used to create a list of the times of executing fibonacci on problems of size 15 16 17 18 19 20 21 22 23 24 25.

   times =: time "1 (11 10 $ 'fibonacci ') ,. format 11 1 $ 15 + i. 11
   times
0.030072 0.048091 0.077764 0.125323 0.203099 0.328096 0.526294 0.851216 1.37865 2.23347 3.6165

If we divide the list of all but the first times by the list of all but the last times we have:

   (1 drop times) % _1 drop times
1.5992 1.61702 1.61158 1.6206 1.61545 1.60409 1.61738 1.61963 1.62004 1.61923

This tells us that the ratio of the time it takes to calculate one term in the fibonacci series is about 1.61442 (the average of the above ratios, the actual explicit solution is 0.5 * 1 + 5 ^ 0.5 which equals 1.61803) larger than the time it takes to calculate the previous term in the fibonacci series.

All this means that the execution time of fibonacci is exponential (approximately 1.61442ⁿ) which is clearly greater than any polynomial in n. Hence, the fibonacci function above is an example of an intractable computation.

10.3.2 The Towers of Hanoi

An ancient legend describes the activities of some monks in a far away place who are engaged in the task of moving 64 disks of increasing size from one of three pegs to another. The ground rules of this task are that only one disk may be moved at a time and putting a larger disk on top of a smaller disk is not allowed. It is said that time will end when the monks finish this task.

Suppose we wish to move one disk from peg a to peg c. This is an easy task; just move the disk from a -> c.

Next, consider the problem of moving two disks from peg a to peg c.

The moves would be a -> b

a -> c

and b -> c.

The problem of moving three disks from a -> c is a bit more complex. However, it can be decomposed into three smaller problems, namely, moving the top two disks from a -> b, moving one disk from a ->c and moving two disks from b -> c.

The moves for this problem are:

a -> c

a -> b, c -> b
a -> c, b -> a
b -> c, a -> c

10.3.3 display-tower-of-hanoi Function

We first define a helping function, show_move, which displays the source pin and destination pin.


show_move =: monad def 'display (0 from y.) , '' -> '' , 1 from y.'

Next we define the function, move, which calculates the moves required for a solution ot the tower of hanoi problem of size n.


move =: monad define
('n' ; 'src' ; 'dst' ; 'hlp') =. y.
if. n = 1
  do. show_move src , dst
  else. move (n - 1) ; src ; hlp ; dst
        show_move src , dst
        move (n - 1) ; hlp ; dst ; src
end.
)

Finally, we define display_tower_hanoi which computes a solution to the tower of hanoi problem.


display_tower_hanoi =. monad def '0$move y. ; ''a'' ; ''c'' ; ''b'''

We now try to analyze display_tower_hanoi to discover the order of execution time for this function. Notice that:


      display_tower_hanoi 1
a -> c

      display_tower_hanoi 2
a -> b
a -> c
b -> c

   display_tower_hanoi 3
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

   display_tower_hanoi 4
a -> b
a -> c
b -> c
a -> b
c -> a
c -> b
a -> b
a -> c
b -> c
b -> a
c -> a
b -> c
a -> b
a -> c
b -> c

   display_tower_hanoi 5
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
a -> b
c -> b
c -> a
b -> a
c -> b
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
b -> a
c -> b
c -> a
b -> a
b -> c
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

A little additional analysis shows that display_tower_hanoi n produces _1+2^n moves. The display-tower-of-hanoi program is intractable since its order is _1+2^n which is exponential (exponential times are always greater that polynomial time).

_1+2^64x ==> 18446744073709551615x

If a workstation can generate 1000 moves per second, it will take that workstation approximately 5,849,424 centuries, 17 years, 129 days, 14 hours, 25 minutes and 52 seconds to generate all of the moves. A workstation which is 1000 times faster (generating 1,000,000 moves per second) would still take more than 5,849 centuries to generate all of the moves!

10.4 Practical Problems Having Intractable Solutions

The traveling salesman problem is the problem of computing the shortest path to visit n cities where each city is connected to every other city by a road. The following diagram shows the problem for n = 5 cities.

A brute-force algorithm exists which computes each possible path. There are 5 ways to choose the first city in a path, 4 ways to choose the second city, etc. Since the path from city a to city b is the same length as that from city b to city a, there are (5 * 4 * 3 * 2 * 1) % 2 paths to consider. For n cities, the brute-force program requires computing the lengths of (fact n) % 2 paths where:

10.4.1 fact Function


fact =: monad define
if. y. < 2
  do. 1
  else. y. * fact y. - 1
end.
)

If n = 20, this algorithm would require computing the lengths of 1216451004088320000 paths between cities. If a workstation can compute the lengths of 10000 paths per second, this algorithm requires approximately 38,573 centuries, 40 years, 302 days, 21 hours, 7 minutes and 12 seconds to finish.

This problem has been studied for more than 50 years and some researchers have found better than brute-force solutions, but no one has found a tractable solution yet! Research continues on this problem.

10.4.2 Minimum Covering Problem

In many manufacturing operations a sheet of material (metal, plastic, cardboard, etc.) must be cut into a given number of different shapes. Of course, the manufacturer wants to minimize the amout of waste material.

Here, the brute-force solution (consider all possible positions of the shapes) is a bit harder to describe, since the object orientation must be considered as well. This problem, as of yet, has no tractable solution.

10.4.3 Game Playing

The problem of choosing the best possible decision in a complex environment, such as business decision making, is very difficult because often the rules governing the decisions are not known or are not well understood. Researchers have studied decision making in simpler situations (that of playing games) where the rules of the game may be precisely stated.

For example, in the game of Checkers, each piece has a small number of moves. At the start of a game, black has 7 possible moves. White has 7 possble responses to some of these moves, but some starting move which black makes have only 2 reasonable responses. It is left as an exercise to the reader to consider some of these possibilities. We can organize the complexity of this decision process by drawing tree diagrams which represent the decision choices.

Samuels, at IBM Research, studied this problem and developed a program which learned to make checkers decisions by playing against a copy of the program which made random choices for moves. The program saved information about decisions which led to wins and learned to avoid decisions which lead to losses. After a learning period of time, the program was able to easily beat Samuels in Checkers games! Brute force attempts to consider all possible choices are clearly intractable.

More complex games, such as Chess, have also been studied. Heuristic algorithms (algorithms which cannot be proven to terminate in a finite amount of time or which do not necessarily lead to an optimal solution) have been used in Chess playing computer programs. Programs exist now which play almost at the Master's level using such methods.

10.5 Summary

One of the main focal points of computer science is the study of algorithms. The limits of computer science are determined largely by our success in finding tractable algorithms and programs. Occasionally we are able to prove that certain problems do not have a computable solution. An example of such a problem is the Halting problem. Given a programming language, P, it has been proved that it is not possible to write a P program which will determine whether or not any given P program halts with an answer after a finite amount of time.

Many problems remain for which only intractable solutions have been found. Such problems provide exciting and challanging research experiences for computer scientists.