Food for Thought: Running Time
Let’s set some ground rules for the discussion of running times of an algorithm.
We'll cover the following
As an algorithm is executed, it consumes system resources like time and memory.
In this course, in particular, we want to be able to talk about how efficient an algorithm is in terms of how much time it takes. So, the first task we undertake is thinking about how to talk meaningfully about the running time of an algorithm.
Time taken by a specific implementation
Does it make sense to define the running time as the number of seconds or nanoseconds taken by a program to run to completion? What if we ran the same program on a faster or a slower machine, or a machine with a different architecture? The running time would be something totally different.
Worse still, even if we ran the program on the same machine, the number of time units taken by it could vary depending on the kind of input fed to it.
In fact, when we want to judge an algorithm in isolation—on its own merit—looking at concrete code implementations of that algorithm can be plain misleading. That’s because, with code implementations, so many other unknowns are thrown into the mix, such as the choice of programming language, optimizations made by the compiler, as well as other implementation-specific choices made by the programmer.
But how can we associate running time with something as abstract as an algorithm written on a piece of paper?
Abstract machine model
We must think about the running time of an algorithm abstractly and independently of any specific hardware.
The computer science community has handled this problem by making some simplifying assumptions about a purely theoretical computing machine—an abstract machine—that will run the algorithm. Such a set of assumptions about an abstract machine is called a machine model.
In this course, we use the random access machine model (RAM model), because it is widely accepted as being sufficiently similar to a simple modern computer and effective for the kinds of analysis we see here.
RAM model
Under the RAM model, we assume that each instruction, executed once, takes a constant amount of time. Such an instruction can use literals, variables, or indexed variables. An instruction is assumed to take some constant amount of time regardless of whether it uses an assignment, comparison, arithmetic, or logic operator. It can also be a conditional or an unconditional branch, such as those seen in the case of an if statement, a function call, or a return statement. For a loop statement, it may be fair to assume that a single execution of the statement takes constant time, but the total time taken over all iterations must add up.
For example, in the snippet given below, as a consequence of the assumptions made under the RAM model, a single execution of each line of code from line 1 to line 5 is assumed to take some constant amount of time. The time to make the function call on line 6 is also assumed to be a constant; but this is in addition to the time taken by the body of the function Foo.
