I have read about big $O$ notation for time complexity and for counting functions like that for prime numbers. Recently on StackOverflow I read:

The problem with defining how long an algorithm takes to run is that you usually can't give an answer in milliseconds because it depends on the machine, and you can't give an answer in clock cycles or as an operation count because that would be too specific to particular data to be useful.


My question is, if we consider an algorithm that is running on a known time complexity (polynomial, linear, etc.) on a machine whose parameters are known, how can we calculate running time in seconds? Essentially, how can time complexity be translated into real time for a given machine?

I ask because I have seen instances where people have said $x$ algorithm will take $y$ time to run.

From what I understand after reading the wikipedia page on time complexity, I would think it is the polynomial value or number of computations divided by the amount of computations a given machine can process per unit time. Is this correct? Is there a general answer?

  • 2
    $\begingroup$ The complexity denoted by big-O only tells you something about the growth of the computation time as the input size grows. This is not enough to conclude the exact running time. $\endgroup$ – SmileyCraft Jan 19 at 20:19

Basically, the concept of time complexity came out when people wanted to know the time dependency of an algorithm on the input size, but it was never intended to calculate exact running time of the algorithm. As it depends on number of factors, like processor, OS, proceses, and many many more..., which all can not be accounted in big-O notation, as it ignores all lower degree terms.

  • 1
    $\begingroup$ That makes sense. From that, I conclude that it is system dependent and cannot be generalized. What about constant time though, where there are no more lower degree terms? $\endgroup$ – Gnumbertester Jan 19 at 20:52
  • $\begingroup$ @Gnumbertester its hard to imagine a algorithm, which is independent of its input, but if there was any such algorithm, that constant must have again have varied with system. and needs to be determined uniquely for each system. i hope it helped :) $\endgroup$ – PranshuKhandal Jan 20 at 2:48
  • $\begingroup$ there do exist algorithms like that also, which are independent of their input size $\endgroup$ – PranshuKhandal Jan 20 at 3:24

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.