Alex Rivera | Logout

What is the difference between time complexity and running time?

Asked 2011-02-06T20:21:20.590
16

What is the difference between time complexity and running time? Are they the same?

Edit
Report

1 Answer

19

Running time is how long it takes a program to run. Time complexity is a description of the asymptotic behavior of running time as input size tends to infinity.

You can say that the running time "is" O(n^2) or whatever, because that's the idiomatic way to describe complexity classes and big-O notation. In fact the running time is not a complexity class, it's either a duration, or a function which gives you the duration. "Being O(n^2)" is a mathematical property of that function, not a full characterisation of it. The exact running time might be 2036*n^2 + 17453*n + 18464 CPU cycles, or whatever. Not that you very often need to know it in that much detail, and anyway it might well depend on the actual input as well as the size of the input.

answered 2011-02-06T20:35:55.070

Your Answer