How to write a unit test to determine if an operation takes about linear time?

Question

I am writing unit tests in JUnit 5 for a Java codebase, though I'm happy to take examples in any language.

I have the ability to count the exact number of times certain operations occur. For the sake of an easy example, let's say the number of comparisons made during a sort.

I'd like to write a unit test that asserts the number of operations performed is in one of four Big Oh complexity classes: constant, linear, nlogn, or quadratic.

So I can, for example, build a list of size 1, sort it, and record the number of operations. Then do the same for a list of size 2, then size 3, etc. The problem is that the relationship between these numbers of comparisons may not be exactly constant, linear, etc. but I want to know which of the four classes they are most like.

What is a good way to detect, while allowing for some error and variation, which of those four classes is the best fit for my sequence of numbers? Ideally, this method would account for amortization.

As an example of amortization, say I want to show that adding an element to an array list takes constant time. The policy for the list is that the array starts at size 5 and doubles each time it fills up. I insert 1 element, then record the number of operations (say memory writes). Insert another element, record the number of operations, and so on for n elements. The number of operations will look something like this:

1, 1, 1, 1, 1, 6, 1, 1, 1...

The 6 occurs when the new array is allocated. This sequence is not exactly constant, but constant is the best fit of the four classes.

EDIT: The best solution I have so far is to find a best fit for an equation of the form:

And then check the constants. If a, b, and c are all close to 0, then the function is constant. If a and b are close to 0, then the function is linear. If a is close to 0, the function is log linear. Otherwise, it is quadratic.

I know this is not a general theoretical solution to the problem in a mathematical sense, but I think this will catch the most common operations for basic data structures and algorithms (lists, binary trees, sorting, minimum spanning trees, etc.).

Answer 1

This is the solution I ended up developing:

For each operation that I want to classify, I take 25 samples and measure the number of relevant operations. For example, I add 25 elements to the middle of an array list and measure how many memory writes occurred each time. Then I look at the relationship between X (1 to 25), Y (operations), delta Y (change in Y), and delta delta Y (change in change in Y).

• If the slope of Y is about 0, then the operation takes constant time: O(1).
• If the slope of Y is increasing, but the slope of delta Y is decreasing, the operation takes logarithmic time: O(lg(n)).
• If the slope of Y is increasing, but the slope of delta Y is about 0, the operation takes linear time: O(n).
• If the slope of Y is increasing and the slope of delta Y is increasing, but the slope of delta delta Y is decreasing, the operation takes log linear time: O(n*lg(n)).
• If the slope of Y is increasing and the slope of delta Y in increasing, and the slope of delta delta Y is about 0, the operation takes quadratic time: O(n^2).
• Other cases are just classified as unknown.

For example:

Memory writes when adding an element to the middle of an array list:
+----+----+---------+---------+
|  x |  y |      dy |     ddy |
+----+----+---------+---------+
|  1 |  1 |         |         |
|  2 |  2 |   1.000 |         |
|  3 |  2 |   0.000 |  -1.000 |
|  4 |  3 |   1.000 |   1.000 |
|  5 |  3 |   0.000 |  -1.000 |
|  6 |  4 |   1.000 |   1.000 |
|  7 |  4 |   0.000 |  -1.000 |
|  8 |  5 |   1.000 |   1.000 |
|  9 | 13 |   8.000 |   7.000 |
| 10 |  6 |  -7.000 | -15.000 |
| 11 |  6 |   0.000 |   7.000 |
| 12 |  7 |   1.000 |   1.000 |
| 13 |  7 |   0.000 |  -1.000 |
| 14 |  8 |   1.000 |   1.000 |
| 15 |  8 |   0.000 |  -1.000 |
| 16 |  9 |   1.000 |   1.000 |
| 17 | 25 |  16.000 |  15.000 |
| 18 | 10 | -15.000 | -31.000 |
| 19 | 10 |   0.000 |  15.000 |
| 20 | 11 |   1.000 |   1.000 |
| 21 | 11 |   0.000 |  -1.000 |
| 22 | 12 |   1.000 |   1.000 |
| 23 | 12 |   0.000 |  -1.000 |
| 24 | 13 |   1.000 |   1.000 |
| 25 | 13 |   0.000 |  -1.000 |
+----+----+---------+---------+
slope of y = 0.525 (increasing)
slope of dy = -0.026 (about constant)
slope of ddy = 0.000 (about constant)
category: O(n)

The only parameter that has to be tuned in this approach is what it means for slope to be "about 0." I have to use different values for different data structures and algorithms. For example, all of my tests with various lists use a value of +-0.05, meaning that slopes between 0.05 and -0.05 are considered a slope of "about 0." For trees, I had to use 0.03, and for hashmaps I had to use 0.2.

Obviously this method is not perfect. As others have pointed out, asymptotic complexity is a theoretical problem, not an empirical one.

However, I was able to successfully unit test the performance of most common operations on common data structures. For example, I can show that insert, find, and remove from array lists and linked lists all have the right linear or constant time performance. I've also tested binary search trees, AVL trees, hash maps, binary heaps, adjacency list and adjacency matrix graphs, disjoint set forests, minimum spanning tree algorithms, and sorting algorithms (though this method proved very brittle for sorting).

This method also works when the theoretical performance relies on amortized analysis. For example, adding to the end of an array list still shows constant time performance even when the array needs to be periodically re-allocated. Same for re-hashing hashtables, though I had to raise the bounds for what counts as "about 0" for the slope quite a bit for it to work properly.

Hope this approach helps somebody else!

Answer 2

First let's start with the boring answer: whether a function belongs in a given complexity class is a purely mathematical concept that cannot be tested for experimentally. Sure you could run the algorithm for n = 100, 200, and 300, and then compare the results somehow, but there is no guarantee that you will get anything interesting out of that.

The more interesting thing to realize is that complexity classes are typically not something your users care about. What they care about is whether the operations they perform take a long time or not. So rather than trying to test for complexity classes, I would rather suggest the following: write a test at the upper limit of how your function is meant to be used (no need to test for n = 1000000 if in practice it never goes above 100) and assert that the time/number of operations it took is under a reasonable upper limit.

So maybe if n is usually under 100, you can test with n = 200, and make sure it performs less than 500 operations (for a linear algorithm). If someone manages to change the algorithm to a quadratic one, that should surely catch it. And if it doesn't, that means the quadratic algorithm isn't actually much worse, so it doesn't matter.

It will be way easier to write such a test, and the test will also be closer to what you actually want to test.