1

I'm currently reading this book called CLRS 2.2 page 25. In which the author describes the Running time of an algorithm as

The running time of an algorithm on a particular input is the number of primitive operations or “steps” executed.

Also the author uses the running time to analyze algorithms. Then I referred a book called Data Structures and Algorithms made easy by Narasimha Karumanchi. In which he describes the following.

1.7 Goal of the Analysis of Algorithms The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of running time but also in terms of other factors (e.g., memory, developer effort, etc.)

1.9 How to Compare Algorithms: To compare algorithms, let us define a few objective measures:

Execution times? Not a good measure as execution times are specific to a particular computer.

Number of statements executed? Not a good measure, since the number of statements varies with the programming language as well as the style of the individual programmer.

Ideal solution? Let us assume that we express the running time of a given algorithm as a function of the input size n (i.e., f(n)) and compare these different functions corresponding to running times. This kind of comparison is independent of machine time, programming style, etc.

As you can see from CLRS the author describes the running time as the number of steps executed whereas in the second book the author says its not a good measure to use Number of step executed to analyze the algorithms. Also the running time depends on the computer (my assumption) but the author from the second book says that we cannot consider the Execution time to analyze algorithms as it totally depends on the computer.

I thought the execution time and the running time are same!

So,

  • What is the real meaning or definition of running time and execution time? Are they the same of different?
  • Does running time describe the number of steps executed or not?
  • Does running time depend on the computer or not?

thanks in advance.

1 Answer 1

3

What is the real meaning or definition of running time and execution time? Are they the same of different?

The definition of "running time" in 'Introduction to Algorithms' by C,L,R,S [CLRS] is actually not a time, but a number of steps. This is not what you would intuitively use as a definition. Most would agree that "runnning" and "executing" are the same concept, and that "time" is expressed in a unit of time (like milliseconds). So while we would normally consider these two terms to have the same meaning, in CLRS they have deviated from that, and gave a different meaning to "running time".

Does running time describe the number of steps executed or not?

It does mean that in CLRS. But the definition that CLRS uses for "running time" is particular, and not the same as you might encounter in other resources.

CLRS assumes here that a primitive operation (i.e. a step) takes O(1) time. This is typically true for CPU instructions, which take up to a fixed maximum number of cycles (where each cycle represents a unit of time), but it may not be true in higher level languages. For instance, some languages have a sort instruction. Counting that as a single "step" would give useless results in an analysis.

Breaking down an algorithm into its O(1) steps does help to analyse the complexity of an algorithm. Counting the steps for different inputs may only give a hint about the complexity though. Ultimately, the complexity of an algorithm requires a (mathematical) proof, based on the loops and the known complexity of the steps used in an algorithm.

Does running time depend on the computer or not?

Certainly the execution time may differ. This is one of the reasons we want to by a new computer once in a while.

The number of steps may depend on the computer. If both support the same programming language, and you count steps in that language, then: yes. But if you would do the counting more thoroughly and would count the CPU instructions that are actually ran by the compiled program, then it might be different. For instance, a C compiler on one computer may generate different machine code than a different C compiler on another computer, and so the number of CPU instructions may be less on the one than the other, even though they result from the same C program code.

Practically however, this counting at CPU instruction level is not relevant for determining the complexity of an algorithm. We generally know the time complexity of each instruction in the higher level language, and that is what counts for determining the overall complexity of an algorithm.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.