Foundations of Computer Science/Algorithm Complexity

Algorithm Complexity

"An algorithm is an abstract recipe, prescribing a process that might be carried out by a human, by computer, or by other means. It thus represents a very general concept, with numerous applications."—David Harel, "Algorithmics - the spirit of computing".

We have learned that algorithms are conceptual solutions to problems. Computing algorithms can be described/defined in terms of the common units of work that computers can do so that they are neutral to programming languages and the execution environment (computers). Algorithm writing is such a creative process as Francis Sullivan noted that "for me, great algorithms are the poetry of computing. Just like verse, they can be terse, allusive, dense, and even mysterious. But once unlocked, they cast a brilliant new light on some aspects of computing." You have seen example algorithms documented using abstract notations such as pseudo code and flowchart.

Once algorithms are implemented/coded, i.e. represented by concrete symbols, they become alive in program that embody them. Programs are executable/runnable by computers. The ability to run different programs that implements all kinds algorithms is a unique feature of computers as machines. Usually when we buy a machine, e.g. an appliance, we assume it has a set of well defined functions it can perform. For example a microwave oven is supposed to warm and cook our food and nothing more. We don't expect a microwave oven ever to be able to wash the clothes for us. A computing machine (a computer) is different. We expect it to perform the function whichever program makes it to do - the functionality of a computer is extensible. If we liken a computer to a car, programmers are drivers who can make the car do different things (to a certain extent) and users are like passengers taking advantage of the things the car can do. This is another reason why everyone needs to learn computer programming because it gives you the freedom to make the computer do different thing.

Correctness of Algorithms

Algorithms must be correct to be useful. We must examine our algorithms carefully to remove errors before using them to create programs. If an algorithm has errors, it is impossible to create correct programs. We often remind students that if their algorithms do not work on paper they won't work on a computer. So we must work out our algorithms on paper first.

Even if the design of an algorithm is correct we may introduce errors during the programming process. As any natural language a programming language has its own syntax consisting of grammatical rules for using the language. When we violate such rules we introduce syntax errors in our program. This type of errors are easy to fix, in fact most modern program editors can detect and warn us about such errors. Another type of errors are logic errors, which result from the misuse of the language. In other words, our grammatically correct program doesn't make sense or make the wrong sense to the computer. For example, a recipe can be unclear or misleading even though all sentences are grammatically correct. You may think that computers can also make mistakes when running programs that are logically. This is true but very rarely this is the case especially with modern computers equipped with error detection mechanisms. We generally assume computers don't make mistakes. If the program doesn't generate the correct answer, it is the result of human errors.

We also call logic errors software bugs. The original "bug" is, in fact, a hardware failure - a moth caught in a electromechanical computer. Now bugs are generally used to refer to any error/failure in computer systems, both in hardware and in software. When a computer program is buggy, it will produce erroneous results or crash as the computer may not know what to do next. Another more subtle bug may cause the computer program to never finish, known as the infinite loop, which is obviously not what we wanted.

Bugs are almost inevitable as humans make mistakes. Then, how do we fix bugs to ensure the correctness of our programs? We must test our programs to verify its correctness. A test consists of a sample input to a program and the desired output from the program. We can run a test by subject the program to the sample input and collect the actual output. If the actual output matches the desired output the program passes the test, otherwise their is a bug in the program or in the test (tests can be buggy too). We usually use a set of tests (a test suite) to exercise different parts of the algorithm. This process is called debugging as expressed in the following pseudo code:

for each test in the test suite
  run and compare the actual output to the desired output
  if they match move on to the next test
  otherwise fix the bug and repeat the whole process

Note that it is very difficult to make our tests exhaustive except for very simple programs. When a program becomes larger and more complex the number of tests need to cover all possible cases grows very fast. As Dijkstra said "program testing can be used to show the presence of bugs, but never to show their absence!" There are techniques for proving the correctness of programs. For instance, microcode for computer processors are often proved correct via formal verification.

"Goodness" of algorithms

There are usually always multiple ways to solve the same problem and, therefore, multiple algorithms to make computers solve the problem for us. In addition to solving the problem correctly we want to be able to compare/evaluate algorithms that solve the same problem. We must define the criteria/measure for "goodness" in algorithm design. Such criteria or measures can include simplicity, ease of implementation, speed of execution, or preciseness of answers. In computing we care the most about the solution speed because a fast algorithm can solve larger problem or more problems in the same amount of time. This is also known as efficiency - an economic measure of many processes. Often time he usefulness of many programs depends on the timeliness of the results. For instance, a program that takes 24 hours to predict the next day's weather is almost useless.

Given an algorithm how do we measure its "speed"? One possible approach is to implement the algorithm, run the result program, and measure its execution time - elapsed time between the start and the end of a program run. There are some challenges in this approach. First the algorithm must be implemented, which can a serious undertaking. Secondly, to run two programs to compare their execution time we must subject them to the same input (a.k.a a workload, e.g a list of one million numbers to be sorted) and the size of the input is never ideal. Thirdly, the "speed" of a running program is influenced by the execution environment, such as the machine's hardware configuration. Take a recipe for example. Different cooks will surely spend different time following it. The amount of food needed will surely magnify the difference - as we increase the amount of ingredients the lengthy recipes will take even longer to follow. But there are intrinsic characteristics of the recipes that affect the preparation time. If a recipe involves beating eggs can instruct the cook to break each egg and scramble it individually or break all eggs first and scramble them together. Obviously the first method is slower due to the additional steps involved. Algorithms in computing exhibit similar characteristics. Recall that algorithms must be defined in terms of the units of work (steps) computers can perform so that it is straightforward to implement them in programming languages. The way the steps are ordered and organized in algorithms can significantly affect the execution time of the programs implement the algorithms.

Since an algorithm is a conceptual solution to a problem, we want to study their "speed" in an abstract sense without actually implementing them. This is known as algorithm analysis in computer science. In this approach we take an algorithm described in pseudo code or flow chart, count the number of steps (units of work), which is always a function of the input size. In the aforementioned example recipe the time it takes to follow the first method (break each egg and scramble it individually) is directly proportional to the number of eggs involved. In fact if only one egg is needed, there is no difference between the two methods. Instead of measuring the steps taken for a particular input size, we focus on the relationship function between the number of steps and the input size, which shows the pattern in which the amount of work (cost) grows as the input size increases. Such functions are also known as growth functions. Then, we apply asymptotic analysis, which compare functions as inputs approach infinity, to simplify the functions because as the input size approaches infinity the difference between the units of works disappears (we can assume breaking an egg and scrambling it take the same amount of time) and the cost of most "complex" part of the task will dominate (a part that repeats a step 10 time will dwarf any step that is only done once) the total cost. For example, in a recipe we have a one quick step (takes 0.0001 seconds per serving) that repeats 10 times and a slow step (takes 10 seconds per serving) doesn't repeat, an amount of serving of N (input size) would cost $0.0001*10*N$ total seconds on the repeated steps and would always cost 10 seconds on the slow step. When N is bigger than 10000, the repeated part would cost more than the slow part. In asymptotic analysis we can ignore the slow step because its contribution to the total cost is negligible when N approaches infinity. With simplify growth functions we can put them into categories considering algorithms in each category to have similar performance characteristics. This type of analysis is not completely precise but it can be very useful in studying the nature of algorithms and predicting their performances. We learn how to put algorithms into categories and rank their performances according to the categories they are in. We denote each category using big O notation.

In summary we have discussed the following few key concepts regarding algorithm complexity analysis:

• Algorithms are conceptual and abstract solutions to problems and programs are concrete executable code computers can run. We can not run algorithms on computers; we can only run programs that implement algorithms. Therefore, the performance of an algorithm is by definition abstract (can not be concretely defined or measured).
• The goodness measure of an algorithm has to be an intrinsic characteristic of the algorithm itself - something that reflects the "cleverness" of the design regardless the implementation details and the future execution environments.
• From an economic perspective we care about the cost of algorithms both in terms of time and space. We will focus only on the time cost in this course. We can not actually measure the time cost of algorithms, but we can study the relationship between the time cost and the input size, which reflects the internal complexity (or cleverness) of algorithms. We represent such relationships as growth functions with the input size as the variable and the total cost as the value. The growth functions can be simplified by keeping only the dominate term (asymptotic analysis) because other terms won't matter when the input becomes really large (eventually approaching infinity). Simplified growth functions are put into categories and algorithms can be rank by the categories they belong to.
• Algorithms in the low complexity category will perform better than algorithms in the higher complexity categories when the input size is sufficiently large. We care about large input sizes because any algorithm can solve a small problem fast. With this algorithm analysis technique we can evaluate and compare algorithms to predict the relative performance of the programs implementing such algorithms before actually implementing any of them.
• Efficiency, as another term often used, is reversely proportional to complexity. A more complex algorithm is less efficient because it makes less efficient uses of the computing resources by being more complex.

Examples

There are at least two ways to calculate the sum of all numbers between 1 and N. The following are two algorithms:

• Algorithm 1: add all the numbers up manually, one by one
• Algorithm 2: calculate the result using this formula $(N+1)*(N/2)$

Consider the following question: if we carry out the two algorithms manually, which one would run faster if

• N = 2?
• N = 100?
• N = 1,000,000?

Lets see how a algorithms behave (after implemented) on a computer. The following script implements algorithm 1 using a block that iterates through all the numbers in the range and adding them to the sum one at a time.

A Snap! script that adds all the numbers between two numbers.

A Snap! reporter block that adds all the numbers between two numbers and reports the sum.

The same problem can be solved using algorithm 2, which use a function to calculate the result as shown in the following script and the report block.

A Snap! reporter block that calculate the sum of all numbers in range and reports the result.

A Snap! block that calculates the sum of all numbers in a range.

Both scripts (programs) take the same input - two numbers that define a range. The number of numbers in the range is the input size or more properly the problem size. We assume the units of work are arithmetic operations $+-*/$, assignment operations, and report operation. Such an assumption is reasonable because in deed those operations takes the same to to perform regardless the operands. If you run the programs and try different input size you will observe that as you increase the input size the execution time of the first program increases steadily whereas the second program shows not change in execution time. Can we predict such behaviors?

Lets apply algorithm analysis to these two algorithms. The first algorithm loops through the numbers to get the sum, therefore the relationship function between cost (the number of steps - additions) and the input size is $f=a+b*N$ assuming N is the input size and a and b are the cost for creating the script variable and the cost for an addition. Note that both a and b are constant because they don't change for a given computer. We can simply the function to $f=N$ because when N approaches infinity the constants don't matter anymore. We assign algorithms with this type of growth function into the leaner algorithm to the leaner this type of functions linear time category denoted by $O(N)$. The second algorithm always takes the same amount of time because it performs the same set of operations regardless of the input size. It belongs to the constant time category denoted by $O(1)$.

Lets consider another problem: are numbers in a list distinct? Here is a straight forward algorithm in pseudo code:

• Step 1: compare the first number with all of the other numbers in the list. If, at any point, the same number is seen, stop and answer NO.
• Step 2: repeat Step 1 by taking the next number from the list and comparing it with all of the other numbers.
• Step 3: after using all numbers in the list, stop and answer YES.

The input size is the size of the list. The more numbers in the list the longer it takes to answer the question. According to algorithm it is possible that the first comparison find two identical numbers, which answer the questions right a way. This is good design because at that point it is unnecessary to continue with the rest of the algorithm. When we analyze algorithms we focus on worst cases because the performance of an algorithm is dependent from the actual input and we should not rely on luck! So the relationship (growth) function between the cost and the input size for this algorithm should be $f=N*(N-1)$ because in the worst case (all numbers are unique) the algorithm has to compare each number to all the other numbers in the list before it arrive at the answer. To simply the function by keeping only the largest dominating term we get $f=N^{2}$, which puts the algorithm in the quadratic category $O(N^{2})$. If you are interested you can reproduce and run the following script (an implementation of the algorithm) to verify the predicted performance characteristics of the algorithm.

A Snap! reporter block that tests whether all the numbers in a list are unique.

A Snap! script that tests whether all the numbers in a list are unique.

Lets look at an algorithm from another category: print all n-digit numbers?

For each number in 0, 1, 2, 3, ..., 9 
 use the number for the first digit
 enumerate all n-1 digit numbers
 append each every n-1 digit number to the first digit to form a n digit number

This example is a little contrived but it demonstrate a new performance category and is very useful when we discuss encryption techniques. The algorithm is complex simply because the amount of output (all n digit numbers) it has to generate. So the cost of the output part will dominate the total cost. To generate all n digit numbers we must first generate all n-1 digit numbers. To generate all n-1 digit numbers we must first generate all n-2 digit numbers and so on. It is easier to study the process backward. Assuming outputting a number is the unit of work (it takes the same time output a number) the cost to generate all one digit numbers is 10. To generate all two digit numbers we have to output $10*10=10^{2}$ numbers. For three digit numbers the cost is $10^{3}$. Did you see a pattern? To generate all n digit numbers it costs $10^{n}$. This type of algorithms goes much faster than the quadratic ones because the input size is in the exponent. They belong to the exponential time category denoted as $O(2^{N})$. The root (in this case 2) doesn't matter. Because all exponential functions are more similar to each other than quadratic functions or linear functions.

Here is a YouTube video illustrating the performance difference between the bubble sort algorithm and the quick sort algorithm: https://www.youtube.com/watch?v=aXXWXz5rF64