2

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?

  • It is obvious, due to the definition of big-O, there cannot be tools which will can prove or disprove a complexity for sure. However, I think the question makes sense if you ask for a tool or method to check the plausibility of a certain complexity by utilizing an implementation. – Doc Brown Jun 18 '16 at 11:09
  • ... the "tool" which you can use for this check is called regression analysis. Of course, you have to produce a set of samples, for example, for the running time, controlled by some "n". – Doc Brown Jun 18 '16 at 11:18
  • @DocBrown Thanks, are you aware of any tools\libraries to perform regression analysis against C# code\console apps? – user87166 Jun 18 '16 at 11:56
  • 1
    Don't expect an out-of-the-box solution. For regression analysis, you can use, for example, MS Excel/and or R (the programming language), see here gardenersown.co.uk/education/lectures/r/regression.htm. To collect the data for that step, you will have to write some code on your own beforehand. If you prefer that, use C#, then it is pretty simple to write a helper program which starts an arbitrary command line program with a certain set of parameters and measure its run time. – Doc Brown Jun 18 '16 at 22:26
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.