Answer to Question #259260 in Algorithms for anju

Question

Explain empirical and theoretical approach for estimating time complexity.

Answer 1

For a theoretical study of the algorithm complexity, it is necessary to calculate the number of operations performed and determine the dependence of this number on the input data size. Because the complexity is determined only up to a factor, then it will be sufficient only to determine how many times the innermost loop is iterated, and how this number is changed with changing data size.

To experimentally investigate the complexity of an algorithm, it is necessary to measure the execution time for different sizes of data sets. These measurements must be carried out for several data sets in order to exclude the influence of external factors as far as the influence of the data quality itself (favorable and unfavorable data for the algorithm) on the measurement results. After that, a graph of the dependence of the execution time on the size of the data is plotted (usually on a logarithmic scale) and the asymptotic complexity of the algorithm may be determined from the slope of this graph.