Given a piece of code, I may use one of many methods to determine the big O complexity of the code manually (runtime and memory).
But, for a given piece of code, how do I determine whether what I found earlier is correct or not? Are there tools available where I give an EXE, give test cases and I get an output saying that the runtime is O(n^2) and memory usage is O(1) for instance?
4
AFAIK, there are no such tools. Google didn’t find one for me. But feel free to look again 🙂
Actually, I wouldn’t expect a standalone tool to either be accurate … or generally useful.
-
It is unlikely to be accurate because there are all sorts of factors in a typical application that distort the performance data that you can measure “from the outside”. For example, the behavior of a typical garbage collector.
-
It is unlikely to be useful for a couple of reasons:
-
Big-O complexity measures are generally applied to specific parts of a program rather than a program as a whole.
-
For a typical program, the scaling parameters involve the size of input files. In most cases, it is not possible for a general “complexity measurement” tool to generate meaningful input files of various sizes.
-
Finally, when we have a complete / working application, the big-O complexity is largely of academic interest. What is really interesting is the actual performance measures; i.e. how much actual time and space is required to run the application for a given dataset / parameters. Big-O complexity doesn’t predict that.
-