Complexity static analyzis of OCaml code

Sometimes, I dream that I am compiling something and the compiler
tells me: “be careful, function F has complexity >= O(n^2)”.

Let’s assume that we have a static analyzer for OCaml code.
Would this analyzis possible?

You should have a look at RAML ( It is I believe the state of the art for automatic analysis of the complexity of OCaml-like programs. You can play with it online. Of course, because the tool is fully automatic, it cannot infer bounds for every programs; AFAIR it is currently limited to (multivariate) polynomial bounds.


The link seems unavailable however the non-HTTPS link works:

1 Like