patternModerate
Why call it 'Time Complexity'?
Viewed 0 times
callwhycomplexitytime
Problem
P.S. I have added the tag 'history', if there is any historical connotation.
Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.
Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.
Solution
Perhaps the earliest place in which time complexity appears is On the computational complexity of algorithms by Hartmanis and Stearns. Their goal is to study computation complexity, which they define as follows:
The computational complexity of a sequence is to be measured by how fast
a multitape Turing machine can print out the terms of the sequence.
Their first section, in which they prove (among else) a time-hierarchy theorem, is about "time-limited computations". They explicitly mention their concept of time:
The machine operation is our basic unit of time.
The reference is to a multitape Turing machine, which they diligently define.
The intention here is to model the running time of algorithms using abstract machines, using number of steps as a proxy for time. Anticipating your criticism, they mention:
Furthermore,
the [complexity] classes are independent of time scale or of the speed of the components from
which the machines could be built, as there is a "speed-up" theorem which
states that $S_T = S_{kT}$ [i.e., $\mathsf{TIME}(T(n))$ = $\mathsf{TIME}(kT(n))$] for positive numbers $k$.
That is, multitape Turing machines can always be sped up by an arbitrary constant, and so there is no harm in associating number of steps with running time, since time complexity classes are "scale free".
The computational complexity of a sequence is to be measured by how fast
a multitape Turing machine can print out the terms of the sequence.
Their first section, in which they prove (among else) a time-hierarchy theorem, is about "time-limited computations". They explicitly mention their concept of time:
The machine operation is our basic unit of time.
The reference is to a multitape Turing machine, which they diligently define.
The intention here is to model the running time of algorithms using abstract machines, using number of steps as a proxy for time. Anticipating your criticism, they mention:
Furthermore,
the [complexity] classes are independent of time scale or of the speed of the components from
which the machines could be built, as there is a "speed-up" theorem which
states that $S_T = S_{kT}$ [i.e., $\mathsf{TIME}(T(n))$ = $\mathsf{TIME}(kT(n))$] for positive numbers $k$.
That is, multitape Turing machines can always be sped up by an arbitrary constant, and so there is no harm in associating number of steps with running time, since time complexity classes are "scale free".
Context
StackExchange Computer Science Q#86683, answer score: 11
Revisions (0)
No revisions yet.