How do I determine correctness of a codes complexity?

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?


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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *