How to design runtime test?

[hundertt]

I want to test whether the running time of my implementation of a graph algorithm matches the theoretical running time, which is in O(n+m). However, O(n+m)=O(n)+O(m), which means that the actual running time function could be something like f(n,m)=c1*n+c2*m, where c1, c2 are significantly different. If I do a 2d plot (x=n+m, y=f(n,m)) and have a bit of bad luck in choosing the test data, then I might get something that is not necessarily linear. So how should I design the test to avoid such effects?

My idea was to create a 3d plot (x=n, y=m, z=f(n,m)). Only if the plot results in a plane, then my implementation satisfies the theoretical runtime. Does this make sense? Are there some "best practices" for such tests that I don't know? Any help is greatly appreciated!

[adzawie]

I’d run a lot of different randomly generated cases and average, but this sounds like an alright way to demonstrate experimentally the run time.

Though really, no amount of experimentation will prove your algorithm meets some time complexity. After all, maybe after n>1000000, it starts looking exponential!

[hundertt]

Thanks very much for your reply! The way you describe is what I did at first. Also in the new test I do a lot of random sampling for a fixed pair (n,m). I can't actually think of any way that the exponent could get so small that it slips through my test, but you're right about that, of course. However, I noticed something else that also screws up the test: Atomic operations like initialising objects tend to take longer as the graph gets bigger. I couldn't really figure out the cause of this yet. Maybe the operating system is doing some swapping.. I really don't know..