document & *test* asymptotic complexity of collection operations

[adriaanm]

I believe there was a framework by @axel22 that does this. Was it scalameter?

See also http://docs.scala-lang.org/overviews/collections/performance-characteristics.html, which should be updated, rendered in the source and then enforced using automated regression testing.

[axel22]

No, ScalaMeter does not do this by default, its main goal is measuring absolute performance numbers.

[adriaanm]

You're right. I was trying to remember which tool measures/tests asymptotic complexity and your name popped up. Have you perhaps authored something else that does this? :-) Or does it ring a bell?

[axel22]

No, I didn't do anything like that. I think @jsuereth did something in that direction. Or maybe Rex Kerr? Not sure. :/

[adriaanm]

Ok, thanks! Rex did https://github.com/Ichoran/thyme, but I don't think that does O(n) either. Maybe I'm just wishful remembering :-)