Re:Is there a way to calculate approximate running time of a...
by gus_massa on Monday August 17, 2015 @08:10AM
(#10072468)
It's almost impossible, but you can get some back of the envelope estimations that are not useful for any serious use.
First you need to know the constant that is in front of O(n^k).
If you are optimistic, the run time is T ~= A * n^k + B n^(k-1) + ...
For simplicity, just drop the B and all the term of smaller order. So T ~= A * n^k
As a rule of thumb, I use that a program where n^k = 10^9 will run in a few seconds, so A=10^-9. (Ten years ago, I use to estimate that A~=10^-6, but now the computers are faster.)
This heavily depends on the computer and language and which is the actual operation that the program is repeating. So it's useful to run a few test with small numbers to get a runtime of a few seconds and estimate the value of A for each case.
In particular, my netbook is 4 times slower than my desktop. You can get the constants ratio between your favorite languages. So remember that A is only an approximation that changes from case to case.
But there are some other problems, for example when the number increase you begin to have problems with the garbage collector, malloc, memory cache, disk cache, ...
Sometimes small cases enter in the microprocessor's cache but big cases need to be swapped to disk. If you draw T vs n you will see that the curve is not smooth, but have a few jumps. (I like log-log graphics.)
And there are weird cases, for example the time constant can be different for even and odd n, or other unexpected conditions.
For example, I remember a Fortran program for something like matrix multiplication where the time was much bigger when n was a power of 2, like 64 or 128, ... (i.e. the run time of 65 was smaller than the run time of 64) I guess it was bad for the cache. But the problem disappear with -O3, because it automatically transpose the matrix, or make it bigger to avoid cache alignment or some other kind of magic.
First you need to know the constant that is in front of O(n^k).
If you are optimistic, the run time is T ~= A * n^k + B n^(k-1) + ...
For simplicity, just drop the B and all the term of smaller order. So T ~= A * n^k
As a rule of thumb, I use that a program where n^k = 10^9 will run in a few seconds, so A=10^-9. (Ten years ago, I use to estimate that A~=10^-6, but now the computers are faster.)
This heavily depends on the computer and language and which is the actual operation that the program is repeating. So it's useful to run a few test with small numbers to get a runtime of a few seconds and estimate the value of A for each case.
In particular, my netbook is 4 times slower than my desktop. You can get the constants ratio between your favorite languages. So remember that A is only an approximation that changes from case to case.
But there are some other problems, for example when the number increase you begin to have problems with the garbage collector, malloc, memory cache, disk cache, ...
Sometimes small cases enter in the microprocessor's cache but big cases need to be swapped to disk. If you draw T vs n you will see that the curve is not smooth, but have a few jumps. (I like log-log graphics.)
And there are weird cases, for example the time constant can be different for even and odd n, or other unexpected conditions.
For example, I remember a Fortran program for something like matrix multiplication where the time was much bigger when n was a power of 2, like 64 or 128, ... (i.e. the run time of 65 was smaller than the run time of 64) I guess it was bad for the cache. But the problem disappear with -O3, because it automatically transpose the matrix, or make it bigger to avoid cache alignment or some other kind of magic.