1
$\begingroup$

In the analysis of algorithms textbooks that I've seen, as far as I could tell, the runtime of an algorithm is defined intuitively. Is there a simple formal definition of this concept? I.e. a definition which fully formally, for some particular simple and general programming language defines the runtime of a program in that language?

$\endgroup$
2
  • 1
    $\begingroup$ Not really. The underlying machine model is the word RAM, but the model is not typically defined formally. $\endgroup$ Apr 14, 2022 at 9:46
  • $\begingroup$ The runtime of a particular kind of Turing machine, such as this one. However, it is somewhat different from the algorithm runtime usually used to analyze an algorithm. $\endgroup$
    – John L.
    Apr 14, 2022 at 20:36

2 Answers 2

1
$\begingroup$

The runtime of an algorithm is naturally nothing but the sum of the runtimes of the individual operations that are performed. This assumes that execution takes place on a machine for which the individual times are known (and usually constant).

One example of such a machine is the MIX computer defined by Knuth.


In a very simple setting, every operation counts for one unit. But there is no universal definition, running time units are ad hoc. The same goes about space complexity: there is no universal definition of the unit of storage.


In the complexity analysis, it is rather exceptional that a detailed account of all instruction be made. On the opposite, one usually focuses on a single type of operation (such as comparisons, floating-point additions, data moves...) and just count their number, assuming that the amount of other operation is at most proportional. By a language abuse, these counts can be considered as running time.


Needless to say, the modern computers are far from being modelled by constant time operations, due to their complex pipelined operation, as well as sophisticated memory hierarchies. Predicting the running time on a real machine is simply impossible, and even non-deterministic.

$\endgroup$
0
$\begingroup$

You may want to reference here if you are still learning about runtime of an algorithm. 'Intuitively' sounds as if you are making a claim calculating the runtime of an algorithm occurs is a loose sense, where in actually the calculations can be very accurate. Consider calculating parallel vs serial. Serial code runs in O(1) for each line, where the number of parallel instances multiplies this by the number of instances.

Adding in functions with loops or recursive calls could move the runtime for certain lines of code up. This is just an example, though many program's runtime can be calculated very precisely.

$\endgroup$
2
  • 2
    $\begingroup$ I am afraid for OP who has used Isabelle/HOL and for many users here in general, "formal definition" means something more formal than the reference mentioned here. By the way, it is unlikely that OP is "still learning about runtime of an algorithm". $\endgroup$
    – John L.
    Apr 15, 2022 at 1:51
  • $\begingroup$ @JohnL. that's right. $\endgroup$
    – user56834
    Apr 15, 2022 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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