Informally, an algorithm can be said to exhibit a growth rate on the order of a mathematical function if beyond a certain input size n, the function times a positive constant provides an upper bound or limit for the run-time of that algorithm. In other words, for a given input size n greater than some n0 and a constant c, the running time of that algorithm will never be larger than . This concept is frequently expressed using Big O notation. For example, since the run-time of insertion sort grows quadratically as its input size increases, insertion sort can be said to be of order Assuming the execution time follows power rule, t ≈ k na, the coefficient a can be found by taking empirical measurements of run time In other words, this measures the slope of the empirical line on the log–log plot of execution time vs. problem size, at some size point. If the order of growth indeed follows the power rule the empirical value of a will stay constant at different ranges, and if not, it will change and the line is a curved line – but still could serve for comparison of any two given algorithms as to their empirical local orders of growth behaviour. Applied to the above table
The loops in steps 4, 5 and 6 are trickier to evaluate. The outer loop test in step 4 will execute times note that an extra step is required to terminate the for loop, hence n + 1 and not n executions, which will consume time. The inner loop, on the other hand, is governed by the value of j, which iterates from 1 to i. On the first pass through the outer loop, j iterates from 1 to 1: The inner loop makes one pass, so running the inner loop body consumes T6 time, and the inner loop test consumes 2T5 time. During the next pass through the outer loop, j iterates from 1 to 2: the inner loop makes two passes, so running the inner loop body consumes 2T6 time, and the inner loop test consumes 3T5 time.
Analysis of algorithms typically focuses on the asymptotic performance, particularly at the elementary level, but in practical applications constant factors are important, and real-world data is in practice always limited in size. The limit is typically the size of addressable memory, so on and on 64-bit machines Thus given a limited size, an order of growth can be replaced by a constant factor, and in this sense all practical algorithms are O for a large enough constant, or for small enough data.
This interpretation is primarily useful for functions that grow extremely slowly: is less than 5 for all practical data is less than 6 for virtually all practical data and binary log is less than 64 for virtually all practical data An algorithm with non-constant complexity may nonetheless be more efficient than an algorithm with constant complexity on practical data if the overhead of the constant time algorithm results in a larger constant factor, e.g., one may have