Section 2.2 What Is Algorithm Analysis?
It is very common for beginning computer science students to compare their programs with one another. You may also have noticed that it is common for computer programs to look very similar, especially the simple ones. An interesting question often arises. When two programs solve the same problem but look different, is one program better than the other?
In order to answer this question, we need to remember that there is an important difference between a program and the underlying algorithm that the program is representing. As we stated in Chapter 1, an algorithm is a generic, step-by-step list of instructions for solving a problem. It is a method for solving any instance of the problem so that given a particular input, the algorithm produces the desired result. A program, on the other hand, is an algorithm that has been encoded into some programming language. There may be many programs for the same algorithm, depending on the programmer and the programming language being used.
To explore this difference further, consider the function shown in Listing 2.2.1. This function solves a familiar problem, computing the sum of the first n integers. The algorithm uses the idea of an accumulator variable that is initialized to 0. The solution then iterates through the n integers, adding each to the accumulator.
Aside
Now look at the method in Listing 2.2.2. At first glance it may look strange, but upon further inspection you can see that this function is essentially doing the same thing as the previous one. The reason this is not obvious is poor coding. We did not use good identifier names to assist with readability, and we used an extra assignment statement that was not really necessary during the accumulation step.
fun foo(tom: Int): Long {
var fred = 0L
for (nancy in 1..tom) {
var joanne = nancy
fred = fred + joanne
}
return fred
}
fun main() {
println(foo(10))
}
The question we raised earlier asked whether one method is better than another. The answer depends on your criteria. The function
sumOfN is certainly better than the function foo if you are concerned with readability. In fact, you have probably seen many examples of this in your introductory programming course since one of the goals there is to help you write programs that are easy to read and easy to understand. In this course, however, we are also interested in characterizing the algorithm itself. (We certainly hope that you will continue to strive to write readable, understandable code.)
Algorithm analysis is concerned with comparing algorithms based upon the amount of computing resources that each algorithm uses. We want to be able to consider two algorithms and say that one is better than the other because it is more efficient in its use of those resources or perhaps because it simply uses fewer. From this perspective, the two methods above seem very similar. They both use essentially the same algorithm to solve the summation problem.
At this point, it is important to think more about what we really mean by computing resources. There are two different ways to look at this. One way is to consider the amount of space or memory an algorithm requires to solve the problem. The amount of space required by a problem solution is typically dictated by the problem instance itself. Every so often, however, there are algorithms that have very specific space requirements, and in those cases we will be very careful to explain the variations.
As an alternative to space requirements, we can analyze and compare algorithms based on the amount of time they require to execute. This measure is sometimes referred to as the execution time or running time of the algorithm. One way we can measure the execution time for the function
sumOfN is to do a benchmark analysis. This means that we will track the actual time required for the program to compute its result. In Java, we can benchmark a function by noting the starting time and ending time within the system we are using. In the System module there is a method called nanoTime that will return the amount of time that the Java virtual machine has been running, in nanoseconds. By calling this function twice, at the beginning and at the end, and then computing the difference, we can get the number of seconds (fractions in most cases) for execution.
Listing 2.2.3 lets you enter the number you want to sum up to (n). It then invokes the
sumOfN method 25 times and calculates the time required for each trial:
import kotlin.time.measureTimedValue
import kotlin.time.DurationUnit
fun sumOfN(n: Int): Long {
var theSum = 0L
for (i in 1..n) {
theSum = theSum + i
}
return theSum
}
fun main() {
print("Find sum from 1 to n: ")
val n = readln().toInt()
for (trial in 0..<25) {
val (result, elapsedTime) = measureTimedValue {
sumOfN(n)
}
println(String.format(
"Trial %2d: Sum %d: time %s",
trial,
result,
elapsedTime.toString(DurationUnit.MILLISECONDS, 4)))
}
}
In Listing 2.2.3, the
main function makes use of Kotlin’s measuredTimedValue function, which is used for timing code. Here is the start and end of the output when we enter 100000 for the limit of the sum:
Trial 0: Sum 5000050000: time 1.7928ms Trial 1: Sum 5000050000: time 0.2238ms Trial 2: Sum 5000050000: time 0.2148ms Trial 3: Sum 5000050000: time 0.3087ms ... Trial 20: Sum 5000050000: time 0.0305ms Trial 21: Sum 5000050000: time 0.0305ms Trial 22: Sum 5000050000: time 0.0305ms Trial 23: Sum 5000050000: time 0.0382ms Trial 24: Sum 5000050000: time 0.0305ms
Why does the time go down from 1.7929ms (that’s microseconds) to 0.0305ms? Because the Kotlin Virtual machine and the computer hardware itself cache results, keeping them in memory for future access. We run the trial loop 25 times in order to give the cache time to stabilize.
We discover that the time is fairly consistent and it takes on average about 0.03 microseconds to execute that code. What if we run the function adding the first 1,000,000 integers? (Showing only the final five trials)
Trial 20: Sum 500000500000: time 0.2972ms Trial 21: Sum 500000500000: time 0.2971ms Trial 22: Sum 500000500000: time 0.3560ms Trial 23: Sum 500000500000: time 0.4551ms Trial 24: Sum 500000500000: time 0.3301ms
This time, the time required for each run is longer, and averages approximately 10 times more seconds. For
n equal to 10,000,000 we get:
Trial 21: Sum 50000005000000: time 3.1218ms Trial 22: Sum 50000005000000: time 2.9680ms Trial 23: Sum 50000005000000: time 2.9839ms Trial 24: Sum 50000005000000: time 3.2700ms
The average again turns out to be about 10 times the previous experiment.
Now consider Listing 2.2.4, which shows a different means of solving the summation problem. This method,
sumOfNImproved, takes advantage of a closed equation \(\sum_{i=1}^{n}
i = \frac {(n)(n+1)}{2}\) to compute the sum of the first n integers without iterating.
fun sumOfNImproved(n: Long): Long {
val theSum = n * (n + 1) / 2
return theSum
}
We then change the call in line 19 of Listing 2.2.3 to:
sumOfNImproved(n)
If we do the same benchmark measurement with this revised code, using four different values for
n (100,000, 1,000,000, 10,000,000, and 100,000,000), we get the following results from averaging the last five trials:
Sum 5000050000: time 0.0012ms Sum 500000500000: time 0.0011ms Sum 50000005000000: time 0.0014ms Sum 5000000050000000: time 0.0011ms
There are two important things to notice about this output. First, the times recorded above are shorter than any of the previous examples. Second, they are very consistent no matter what the value of
n. It appears that sumOfNImproved is hardly impacted by the number of integers being added.
But what does this benchmark really tell us? Intuitively, we can see that the iterative solutions seem to be doing more work since some program steps are being repeated. This is likely the reason it is taking longer. Also, the time required for the iterative solution seems to increase as we increase the value of
n. However, if we ran the same function on a different computer or used a different method language, we would likely get different results. It could take even longer to perform sumOfNImproved if the computer were older.
We need a better way to characterize these algorithms with respect to execution time. The benchmark technique computes the actual time to execute. It does not really provide us with a useful measurement because it is dependent on a particular machine, program, time of day, compiler, and programming language. Instead, we would like to have a characterization that is independent of the program or computer being used. This measure would then be useful for judging the algorithm alone and could be used to compare algorithms across implementations.
You have attempted of activities on this page.
