Unit tests to verify time complexity

Question

Hi, Does anyone use unit tests to verify the time/space complexity of code?

Thanks

Hugo

Answer 1

That's a perfectly good point you bring up. Sure you use Unit test for this.

A unit test is mainly a "way" of testing the outcome of your code. You test if it does what it is supposed to do and that it fails when you want it to fail.

Time and Space is two variables that are highly important and you might "want" fast speed and low space cost but the program actually does the opposite, then you got a bug, this is what the unit test are for, to find bugs and solve them.

Some Pseudo Code of a Unit test for time Consuming, you might know how to solve this, but this is a fairly nice way of testing it:

Unit_Test_To_See_If_X_Takes_More_Than_Y_Seconds(int max_milli_seconds)
{
    int current_millis = getMillis();

    do_operations_on_objects_and_functions();

    int millis_after_executions = getMillis();

    int elapes_millis = millis_after_execution - current_millis;

    if ( elapsed_millis > max_milli_seconds )
      Assert(ERROR);

}

Also when you think about it, can you have too many tests? No you can't. It's good to test for all outcomes, even if you test for "stupid" things, if you don't test for an outcome and a bug is evolved, does it mean that it doesn't exist just because you didn't see it or you didn't test for it? :)

Answer 2

Possible solution would be to test with Filip's function with 1 iteration, then 100, then 1000, then 10000 (etc) and plot the results on a graph to determine the time complexity. Or use maths to derive the highest factor difference between each run. I'm not sure how you'd test space however.

I don't think the output would be a simple pass or fail unless there's an existing algorithm to derive the highest factor (N^2 etc) and compare against that.

Answer 3

I had a similar problem when i was tuning an algorithm. What I did was to loop it and then divided by the number of loops and the big-O value. Then, I called this "q" or "quality value". Interestingly, the value was more or less constant as I expected, and a bit higher for bad parameters. The point is, if you look at the definition of big-O, that you get a measurement of the "less dominant" calculations beside the main one. They are often constant or have lower complexity. In my case, it was a bit linear but still nothing to think about.

My suggestion is, to calculate such quality-values. Then you can see if there is a sudden raise which indicates a side effect of your last changes that breaks your complexity assumption.

Answer 4

While the time aspect is pretty well covered Filip's and Josh's answer, the space issue is more complex, as the code in question is liable to release any memory and resources it used on completion. Thus I would guess that unit testing is not particularly useful by itself for determining space complexity. You would need either a probe, or some other monitor running asynchonously with your coude being tested.

I would say providing some in-situ logs / traces in the code being tested would be the easiest solution, possibly removed from the release build.