Calculating Running time from Time ComplexityI 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.https://stackoverflow.com/questions/11806021/how-does-one-calculate-the-runtime-of-an-algorithmMy 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?

Question

Calculating Running time from Time ComplexityI 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&#039;t give an answer in milliseconds because it depends on the machine, and you can&#039;t give an answer in clock cycles or as an operation count because that would be too specific to particular data to be useful.https://stackoverflow.com/questions/11806021/how-does-one-calculate-the-runtime-of-an-algorithmMy 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?

Ryan Newman · Accepted Answer

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.

Calculating Running time from Time Complexity I have read about big O notation for time complexity

Answered question

Answer & Explanation

New Questions in Pre-Algebra