Using timer information to calculate O complexity

[Mike Pliam]

Hi.

I have a wonderful little hires_timer.h that I got quit a while back from Gabriel Fiescu and others. I love this thing because it reads out and saves the number of CPU cycles that it takes to do something, simply by including the header and using the macros:


#include "hires_timer.h"

//
int main()
{
//..
PERF_DECLARE

PERF_START
// do something here
PERF_STOP
PERF_REPORT
PERF_SAVE


return 0;

}



Anyway, by repeatedly running the app one can repeatedly append the cycles required to perform the 'something'.

My question is, given a set of numbers, each of which represent the cycles required to run the 'something', and given that the something function has an input parameter 'N', then how does one calculate the complexity in 'O' notation as it relates to N.

For example, here's a set of ncycles that I obtained by running a multiple precision factorial(N) function (this is saved in a text file - it is not code.)

mpFactorial(1000)
440515817
468624723
446289207
451692185
448908264
469676438
449398453
452693052
447862688
450112222
454507025
458702839

mpFactorial(2000)
903331772
893319588
888749834
896593600
931249809
884259320
887267514
885304721
888507088
888604696

mpFactorial(3000)
1380426075
1385679456
1387957263
1384936791
1404893434
1382351796
1370519731
1389585785
1367907016
1382329550
1379572033
1382004022
1370687045

Is there some program available to curve-fit these numbers to approximate the complexity in 'O' notation ? Or do I have to try an write one myself :(

Thanks.

Mike

[JohnyDog]

Well i guess any graph-creating program (excel etc) will do for rough approximation? With one axis beign x (1000,2000,3000) and other axis the average of runtime cycles for that x. If the result is straight ascending line, it is linear complexity, if its parabole it's exponential etc etc. In your example its linear complexity O(n). However complexity should be rather done by analyzing the algorithm in question rather than benchmarking it.

[SuperKoko]

Suggestion :
You may have more accurate results if you increase the priority of your process with SetPriorityClass (under Win32).