Testing computational complexity is a real pain. We can't really test worst case complexity as it depends on the algorithm used. We could try average complexity, but that needs extensive test with big input (because we want the asymptotic complexity). I think it's impossible to test thoroughly on this platform since tests are limited in time.
We could possibly test for an upper bound rather than an asymptotic behavior (no more than 4*n access operation for example), this would allow us to test on smaller set of data. However, that requires to monitor access operation, and it's impossible here. Firstly because some languages like JavaScript don't allow to override array access operators for example, but also because the algorithm being tested might as well work on a copy of the input (converting it into another data structure).
I'd conclude that your initial approach is good enough, as long as it only yields false positives but isn't too restricting to yield false negatives. It's just an incentive to write efficient code :) In the end we're here to train, these are not exams :D

How do we upvote katas in beta process ? I can't find a place where I can click on the upvote counter to add mine. Thank you for your help