Estimating the time complexity of the algorithms by counting the Java bytecode instructions
Tomaž Dobravec · 2017
Ranging the selected algorithms with the same theoretical time complexity boundaries can only be done by comparing the behavior of their implementations in the real environment. Timing the algorithms in practice is very difficult since it is hard to ensure a fair and reproducible environment in which implementations can be compared. In this paper we present a system called ALGator that was developed to facilitate the process of testing, comparing and evaluating the algorithms. Besides the time complexity indicators, ALGator also measures the usages of the Java bytecode instructions. We present the usage of the ALGator's JVM indicators for the estimation of the time complexity of selected bytecode instructions. We also present a method to predict the behavior of the simple algorithm for matrix multiplication using the results of the JVM indicators analysis.