5
$\begingroup$

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.

Improve this question
$\endgroup$
  • 2
    $\begingroup$ I'm not sure if this question can be answered objectively. I'd guess that the reference to time can be explained by the fact that we'd like to know the precise time, but unfortunately cannot reason with it properly, so we simply take the best predictor we know for execution time that can be reasoned with: the execution step count. But my guess is as good as any. I doubt this can be decisively answered unless a clear historical motivation is found. $\endgroup$ – Discrete lizard♦ Jan 13 '18 at 12:39
  • $\begingroup$ That is true. So far, I understood that they (analysts) avoided unwanted complexity involved for calculating actually time of an algorithm (or to say program) to execute like internal process call etc., they figured dominating function. But, why call it time-complexity is creating lot of confusion in the mind of fresher in the field. $\endgroup$ – Ubi hatt Jan 13 '18 at 12:58
  • 4
    $\begingroup$ You can also ask, why "complexity" when we're actually interested in "cost"? $\endgroup$ – Raphael♦ Jan 13 '18 at 14:02
  • $\begingroup$ No, I am actually interested in terminology of 'Time Complexity'. Actually, I thought to tag you in post. Thanks you noticed $\endgroup$ – Ubi hatt Jan 13 '18 at 14:30
  • 1
    $\begingroup$ @UKB I don't think anyone's claiming that "step" is vague. People are complaining that "step complexity" is vague because it could mean "complexity measured by number of steps" or "complexity of an individual steps" (as in, "there are only three steps in this algorithm, but one of them is very complex"). $\endgroup$ – David Richerby Jan 13 '18 at 16:20
10
$\begingroup$

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".

Improve this answer
$\endgroup$
  • $\begingroup$ Nice! I really appreciate your answer. So, far your answer has some relevance. I was/is miffed by the confusion it creates for fresher or up to some extant intermediate level CS students. Literary, first impression is to find actual time. But again, I would like to say that I don't need physical machine to run algorithm. In fact, you can't run algorithm (pseudo-code) on physical machine until we translate into some programming language. We work on piece of paper and suppose, input = n (max). So, where is time involved?. Time comes in picture, if program is ran on machine. $\endgroup$ – Ubi hatt Jan 13 '18 at 16:20
  • 1
    $\begingroup$ The program does run on a machine - an abstract machine like a RAM machine. The RAM machine is a good model for CPUs, and algorithms can typically be converted from a textual description based on the RAM machine model to C programs without loss of efficiency. $\endgroup$ – Yuval Filmus Jan 13 '18 at 16:35
  • $\begingroup$ Yes, I agree that we don't loose any efficiency, if translated to C or any other program. But don't you think there should be difference in view from Mathematical and CS point of view? Because, if I as CS student design algo to calculate factorial and show it to you. You will say it has complexity of n!, that's it. N! is mathematical function and I don't relation of time with these mathematical functions (n, $n^2, n!$ etc.,) $\endgroup$ – Ubi hatt Jan 13 '18 at 16:48
  • 2
    $\begingroup$ Computer science is a mathematical area. I don't see any need to artificially distinguish between the two. It seems like you have some misconceptions you have to overcome. $\endgroup$ – Yuval Filmus Jan 13 '18 at 18:08
  • 3
    $\begingroup$ This discussion seems to be losing focus. You've made your talking point. Personally, I disagree with it, but ultimately it's a subjective matter. You're entitled to your opinion, but don't expect to convince me. $\endgroup$ – Yuval Filmus Jan 13 '18 at 18:17
3
$\begingroup$

I think, though I don't have any references to back this up, that it's just a convenient name that has a ring of truth to it.

If you imagine implementing a standard Turing machine, it does seem reasonable that every step of your actual, physical machine will take the same amount of time. So, for a Turing machine, time and number of steps are the same thing, up to a constant factor. That isn't true for more complicated machines – for example, a single step of a RAM could involve moving the tape heads an arbitrary distance – but the analogy is good enough.

All names seem to have disadvantages. "Time complexity" sounds like it's measured in seconds. Something like "step complexity", "operation complexity" or "instruction complexity" might be misunderstood as referring to the complexity of the individual steps, rather than to complexity measured by the number of steps. But these aren't big disadvantages: it only takes a moment to explain that "time" doesn't literally mean time or that "step complexity" doesn't mean the complexity of the steps.

If we were starting again from scratch, I think either "time complexity" or "step complexity" would be a reasonable name. I can't think of any other term that's both reasonably short and more accurately conveys the concept of complexity measured in terms of the number of computational steps.

And be thankful that we didn't call it "type 1" complexity. I'm looking at you, statistics and diabetes.

Improve this answer
$\endgroup$
  • $\begingroup$ I rather say that 'Time complexity' creates more confusing. I have seen people in real life and online (mainly fresher) asking for actual way of calculating time and other person providing answer by saying that keep a start timecounter and end timecounter and measure time (I'm not joking). Majority of standard text books talk about steps (operations) we are concern with and it became very clear when we understand that we are actually calculating steps of mathematical function involve. So, we don't have to worry about internal operation. Because we can workout on piece of paper. $\endgroup$ – Ubi hatt Jan 13 '18 at 14:53
  • $\begingroup$ Typo "confusing" should be "confusion". Also, I am not hypnotizing anything. I am interested in Terminology rather than proving something. $\endgroup$ – Ubi hatt Jan 13 '18 at 15:02
  • $\begingroup$ @UKB The reference to statistics and diabetes are pointing to some completely terrible naming conventions. Statisticians call false positives and false negatives type-1 and type-2 errors; clinicians call diabetes caused by losing the ability to produce insulin and caused by losing the ability to respond to insulin type-1 and type-2 diabetes. These are terrible names because the name does nothing at all to remind you of its meaning. At least "time complexity" and "space complexity" remind you what they mean when you say them. $\endgroup$ – David Richerby Jan 13 '18 at 15:10
  • $\begingroup$ I don't see same problem here. While studying time-complexity we emphasis more on mathematical functions and then we discard insignificant terms and stress more one steps or operation involve in most significant term. I don't relate to that thought $\endgroup$ – Ubi hatt Jan 13 '18 at 15:21
  • $\begingroup$ The same problem as what? $\endgroup$ – David Richerby Jan 13 '18 at 16:20
2
$\begingroup$

Time complexity is a formal model (an abstraction) of program running time. Although on the face of it you are right that it really measures the number of steps, it is asymptotically no different from the actual running time of the machine (Turing machine or any other model of computation). Therefore I disagree that there is any problem with the terminology.

Think about it from the programmer's perspective. When you write a piece of code, say

 for i = 1 ... n :
     for j = 1 ... i :
          print j
     print newline

you can't (as a programmer) actually predict how long the program will take to run in seconds, with accuracy. Moreover the number of seconds depends on the exact platform on which you run the code, level of parallelization, what file or output you are printing to, etc.

But what you can measure is the number of steps your code runs -- that is, its time complexity, as a function of $n$. You simply count the number of times a print statement is executed. This is -- up to a constant -- a good and correct estimate of the actual time the program will take to run, in seconds.

In summary, the concept of time complexity is exactly the same concept that programmers use to think about their code's performance, and the abstraction is the same as the actual running time up to a constant.

Improve this answer
$\endgroup$
0
$\begingroup$

From what I can tell, your appeal to the terms "step complexity" and "operation complexity" are a way of attaining a more objective definition of an alogithm's behavior, without tying it down to the actual execution time of the algorithm on an arbitrary machine.

However, "step" and "operation" are not so objective, either. Different CPUs can have vastly different instruction sets. For example, in the x86 instruction set, MOV EAX, [EDX + EBX*4 + 8] is a single instruction! That's despite it doing 1 multiplication, 3 additions, and 1 move.

Perhaps you could say "okay, well then we'll count it as 5 operations." Well that gets really complicated, too. These could very well be done in one shot by hardware, or perhaps as a decomposition of simpler instructions as orchestrated by the processor's microcode. Not only is it not defined which of these two approaches a processor uses, but the notion of these "simpler instructions" is also blurred. Who's to say multiplication is a single instruction? It could be implemented as a sequence of additions, for all you know (it's not, don't worry, but the point stands).

Anyhow, talking about "time complexity" makes sense, because we don't really care about steps or operations. What we really care about is how steps or operations can be used as a proxy for time. E.g. we don't care if one algorithm takes 10 steps or another takes 20, if the first algorithm takes 10 seconds and the other takes 2 seconds.

Improve this answer
$\endgroup$
  • $\begingroup$ My explicit concern is this "...I just want to understand that what is the role of 'Time' in 'Time Complexity' and why we call it 'Time Complexity’...". Secondly, I guess you missed the core point. Because we don't care about CPU operations. I covered up that part saying I am assuming RAM model. Can you tell me, what concerns you more while finding element 'x' in sorted array, 1) amount of time taken by program or 2) number of steps involve? $\endgroup$ – Ubi hatt Jan 13 '18 at 17:03
  • $\begingroup$ @UKB "..I just want to understand that what is the role of 'Time' in 'Time Complexity' and why we call it 'Time Complexity’..." Time does not determine time complexity, but we use time complexity to estimate time, in relative terms. $\endgroup$ – Alexander Jan 13 '18 at 17:11
  • $\begingroup$ @UKB I don't see what your assumption of the RAM model is meant to imply. If it's to standardize our definition of a "step" or "operation", then it's really rather arbitrary, and it's really just privileging one processor design over the others, arbitrarily. Why didn't you pick UTM instead? Or X86? or ARM? $\endgroup$ – Alexander Jan 13 '18 at 17:13
  • $\begingroup$ @UKB "Can you tell me, what concerns you more while finding element 'x' in sorted array, 1) amount of time taken by program or 2) number of steps involve?" Definitely 1, the amount taken. We care about the number of steps only insofar as it serves as a proxy to predict time. $\endgroup$ – Alexander Jan 13 '18 at 17:14
  • $\begingroup$ how you predict time? that would be more helpful to further understand. $\endgroup$ – Ubi hatt Jan 13 '18 at 18:06
0
$\begingroup$

In practice an actual machine does not spend a particular time for each operation that is equal to any other machines length of time. Hence what we measure is a general trend of growth.

Consider addition on a machine nowadays.

Consider addition on a mechanical computer.

It is not unreasonable to use both as models to measure the length of time an algorithm takes to complete. However, the issue is that both have wildly different EXACT amounts. All we can reason is how changing the input changes the runtime of the algorithm.

A better way to consider is that runtime is a function of the length of time of each step you assume to take one unit of time. Then, time complexity is a result of analyzing that function. In particular because those times will vary from actual machine to actual machine.

I.E. give the abstract machine abstract times to complete each immutable step so that it can apply to any such machine implemented in the real world.

Improve this answer
$\endgroup$

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.