[LRUG] Writing specs for the time-complexity of a method

[Tim Cowlishaw]

Hi all,

This might be a pretty hare-brained idea, but I was wondering if
anyone's ever tried to write specs that test the time complexity of a
given method call?

For reference, I'm currently writing a ruby implementation of the
aho-corasick string matching algorithm [1], the behaviour of which can
be specified by the following rspec specs:
https://gist.github.com/1312065

However, these specs can be vacously satisfied by the following
implementation, which doesn't perform the aho-corasick algorithm, but
instead matches strings by a naive iterative process:
https://gist.github.com/1312074

Now, the motivation for doing this in the first place was in order to
locate all the members of a set of strings which are present in
another string in O(n) time, where n is the length of the string to be
matched against. The naive approach takes O(knm) where n is the length
of the matched string, k is the number of 'candidate' strings in the
set, and m is the average length of a candidate string. Therefore, it
seems to me that I should write a spec which says something like `it
"should take constant time relative to the length of the string to
match'` as this encapsulates my requirements, and doesn't over-specify
the implementation. However, my gut feeling is that this is a pretty
silly idea (and also tricky to implement, as I'd need to build in some
degree of tolerance to the time measurements).

Therefore, does anyone have a better approach for specifying the
required time-complexity of a certain method or process? Or is it just
something that doesn't need testing?

Thanks,

Tim


REFERENCES
---------------------
[1] http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm