testing a custom data structures big-o complexity

Question

As an assignment, I implemented a custom data structure and a few test cases in order to make sure it works properly. The code itself is not really needed for the question but you can assume it is some sort of a SortedList. my problem is that I was also asked to test big-O complexity, e.g make sure put() is o(n) etc.

I am having allot of trouble understanding how can I write such a test.

one way that came to mind was to count the amount of iterations inside the put() method with a simple counter and then checking that it is equal to the size of the list, but that would require me to change the code of the list itself to count the exact number, and I would much rather doing it in a proper way, outside the class, holding only an instance of it.

any ideas anyone? I would really appreciate the help!

Answer 1

Get the current time at the start of the test, call the method that you're testing a large number of times, get the current time after, and check the difference to get the execution time. Repeat with a different size input, and check that the execution time follows the expected relationship.

For an o(n) algorithm, a suitable check would be that doubling the input size approximately doubles the execution time.

Answer 2

With unit testing you test the interface of a class, but the number of iterations is not part of the interface here. You could use a timer to check the runtime behaviour with different sizes. If it's O(n) there should be a linear dependency between time and n.