Editing Analysis of algorithms (section)

==Run-time analysis==
Run-time analysis is a theoretical classification that estimates and anticipates the increase in ''[[DTIME|running time]]'' (or run-time or execution time) of an [[algorithm]] as its ''[[Information|input size]]'' (usually denoted as {{mvar|''n''}}) increases.  Run-time efficiency is a topic of great interest in [[computer science]]:  A [[Computer program|program]] can take seconds, hours, or even years to finish executing, depending on which algorithm it implements. While [[software profiling]] techniques can be used to measure an algorithm's run-time in practice, they cannot provide timing data for all infinitely many possible inputs; the latter can only be achieved by the theoretical methods of run-time analysis.

===Shortcomings of empirical metrics===

Since algorithms are [[platform-independent]] (i.e. a given algorithm can be implemented in an arbitrary [[programming language]] on an arbitrary [[computer]] running an arbitrary [[operating system]]), there are additional significant drawbacks to using an [[empirical]] approach to gauge the comparative performance of a given set of algorithms.

Take as an example a program that looks up a specific entry in a [[collation|sorted]] [[list (computing)|list]] of size ''n''.  Suppose this program were implemented on Computer A, a state-of-the-art machine, using a [[linear search]] algorithm, and on Computer B, a much slower machine, using a [[binary search algorithm]].  [[benchmark (computing)|Benchmark testing]] on the two computers running their respective programs might look something like the following:

{| class="wikitable"
|-
! ''n'' (list size)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in [[nanosecond]]s)
|-
| 16
| 8 
| 100,000 
|-
| 63
| 32 
| 150,000 
|-
| 250
| 125 
| 200,000 
|-
| 1,000
| 500 
| 250,000 
|}

Based on these metrics, it would be easy to jump to the conclusion that ''Computer A'' is running an algorithm that is far superior in efficiency to that of ''Computer B''.  However, if the size of the input-list is increased to a sufficient number, that conclusion is dramatically demonstrated to be in error:

{| class="wikitable"
|-
! ''n'' (list size)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in [[nanosecond]]s)
|-
| 16
| 8 
| 100,000 
|-
| 63
| 32 
| 150,000 
|-
| 250
| 125 
| 200,000 
|-
| 1,000
| 500 
| 250,000 
|-
| ...
| ...
| ...
|-
| 1,000,000
| 500,000
| 500,000
|-
| 4,000,000
| 2,000,000
| 550,000
|-
| 16,000,000
| 8,000,000
| 600,000
|-
| ...
| ...
| ...
|-
| 63,072 &times; 10<sup>12</sup>
| 31,536 &times; 10<sup>12</sup> ns,<br />or 1 year
| 1,375,000 ns,<br />or 1.375 milliseconds
|}

Computer A, running the linear search program, exhibits a [[linear]] growth rate.  The program's run-time is directly proportional to its input size.  Doubling the input size doubles the run-time, quadrupling the input size quadruples the run-time, and so forth.  On the other hand, Computer B, running the binary search program, exhibits a [[logarithm]]ic growth rate.  Quadrupling the input size only increases the run-time by a [[wiktionary:Constant|constant]] amount (in this example, 50,000 ns).  Even though Computer A is ostensibly a faster machine, Computer B will inevitably surpass Computer A in run-time because it is running an algorithm with a much slower growth rate.

===Orders of growth===
{{main|Big O notation}}
Informally, an algorithm can be said to exhibit a growth rate on the order of a [[Function (mathematics)|mathematical function]] if beyond a certain input size {{mvar|''n''}}, the function {{math|''f''(''n'')}} times a positive constant provides an [[Asymptotic analysis|upper bound or limit]] for the run-time of that algorithm.  In other words, for a given input size {{mvar|''n''}} greater than some {{mvar|''n''}}<sub>0</sub> and a constant {{mvar|''c''}}, the run-time of that algorithm will never be larger than {{math|''c'' × ''f''(''n'')}}.  This concept is frequently expressed using Big O notation.  For example, since the run-time of [[insertion sort]] [[quadratic growth|grows quadratically]] as its input size increases, insertion sort can be said to be of order {{math|''O''(''n''<sup>2</sup>)}}.

Big O notation is a convenient way to express the [[Best, worst and average case|worst-case scenario]] for a given algorithm, although it can also be used to express the average-case &mdash; for example, the worst-case scenario for [[quicksort]] is {{math|''O''(''n''<sup>2</sup>)}}, but the average-case run-time is {{math|''O''(''n'' log ''n'')}}.

===Empirical orders of growth===
Assuming the run-time follows power rule, {{math|''t'' &asymp; ''kn''<sup>''a''</sup>}}, the coefficient {{mvar|''a''}} can be found <ref>[http://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ How To Avoid O-Abuse and Bribes] {{Webarchive|url=https://web.archive.org/web/20170308175036/https://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ |date=2017-03-08 }}, at the blog "Gödel's Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick</ref> by taking empirical measurements of run-time {{math|{''t''<sub>1</sub>, ''t''<sub>2</sub>}}} at some problem-size points {{math|{''n''<sub>1</sub>, ''n''<sub>2</sub>}}}, and calculating {{math|1=''t''<sub>2</sub>/''t''<sub>1</sub> = (''n''<sub>2</sub>/''n''<sub>1</sub>)<sup>''a''</sup>}} so that {{math|1=''a'' = log(''t''<sub>2</sub>/''t''<sub>1</sub>)/log(''n''<sub>2</sub>/''n''<sub>1</sub>)}}. In other words, this measures the slope of the empirical line on the [[log–log plot]] of run-time vs. input size, at some size point. If the order of growth indeed follows the power rule (and so the line on the log–log plot is indeed a straight line), the empirical value of {{mvar||''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:

{| class="wikitable"
|-_
! ''n'' (list size)
! Computer A run-time<br />(in [[nanosecond]]s)
! Local order of growth<br />(n^_)
! Computer B run-time<br />(in [[nanosecond]]s)
! Local order of growth<br />(n^_)
|-
| 15
| 7 
| 
| 100,000 
| 
|-
| 65
| 32 
| 1.04
| 150,000 
| 0.28
|-
| 250
| 125 
| 1.01
| 200,000 
| 0.21
|-
| 1,000
| 500 
| 1.00
| 250,000 
| 0.16
|-
| ...
| ...
| 
| ...
| 
|-
| 1,000,000
| 500,000
| 1.00
| 500,000
| 0.10
|-
| 4,000,000
| 2,000,000
| 1.00
| 550,000
| 0.07
|-
| 16,000,000
| 8,000,000
| 1.00
| 600,000
| 0.06
|-
| ...
| ...
| 
| ...
| 
|}

It is clearly seen that the first algorithm exhibits a linear order of growth indeed following the power rule. The empirical values for the second one are diminishing rapidly, suggesting it follows another rule of growth and in any case has much lower local orders of growth (and improving further still), empirically, than the first one.

=== Evaluating run-time complexity ===
The run-time complexity for the worst-case scenario of a given algorithm can sometimes be evaluated by examining the structure of the algorithm and making some simplifying assumptions.  Consider the following [[pseudocode]]:

 1    ''get a positive integer n from input''
 2    '''if''' n > 10
 3        '''print''' "This might take a while..."
 4    '''for''' i = 1 '''to''' n
 5        '''for''' j = 1 '''to''' i
 6            '''print''' i * j
 7    '''print''' "Done!"

A given computer will take a [[DTIME|discrete amount of time]] to execute each of the [[Instruction (computer science)|instructions]] involved with carrying out this algorithm.  Say that the actions carried out in step 1 are considered to consume time at most ''T''<sub>1</sub>, step 2 uses time at most ''T''<sub>2</sub>, and so forth.

In the algorithm above, steps 1, 2 and 7 will only be run once.  For a worst-case evaluation, it should be assumed that step 3 will be run as well.  Thus the total amount of time to run steps 1–3 and step 7 is:

:<math>T_1 + T_2 + T_3 + T_7. \,</math>

The [[program loop|loops]] in steps 4, 5 and 6 are trickier to evaluate.  The outer loop test in step 4 will execute ( ''n'' + 1 )
times,<ref>an extra step is required to terminate the for loop, hence n + 1 and not n executions</ref> which will consume ''T''<sub>4</sub>( ''n'' + 1 ) time.  The inner loop, on the other hand, is governed by the value of j, which [[iteration|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 (step 6) consumes ''T''<sub>6</sub> time, and the inner loop test (step 5) consumes 2''T''<sub>5</sub> 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 (step 6) consumes 2''T''<sub>6</sub> time, and the inner loop test (step 5) consumes 3''T''<sub>5</sub> time.

Altogether, the total time required to run the inner loop ''body'' can be expressed as an [[arithmetic progression]]:

:<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>

which can be [[factorization|factored]]<ref>It can be proven by [[Mathematical induction|induction]] that <math>1 + 2 + 3 + \cdots + (n-1) + n = \frac{n(n+1)}{2}</math></ref> as

:<math>\left[ 1 + 2 + 3 + \cdots + (n-1) + n \right] T_6 = \left[ \frac{1}{2} (n^2 + n) \right] T_6</math>

The total time required to run the inner loop ''test'' can be evaluated similarly:

:<math>\begin{align}
& 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5\\
= {} &T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5
\end{align}</math>

which can be factored as

:<math>\begin{align}
& T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 \\
={}& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + (n + 1)T_5 - T_5 \\
={}& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + n T_5 \\
={}& \left[ \frac{1}{2} (n^2 + 3n) \right] T_5
\end{align}</math>

Therefore, the total run-time for this algorithm is:

:<math>f(n) = T_1 + T_2 + T_3 + T_7 + (n + 1)T_4 + \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2+3n) \right] T_5</math>

which reduces to

:<math>f(n) = \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7</math>

As a [[rule-of-thumb]], one can assume that the highest-order term in any given function dominates its rate of growth and thus defines its run-time order.  In this example, n<sup>2</sup> is the highest-order term, so one can conclude that {{math|1=''f''(''n'') = ''O''(''n''<sup>2</sup>)}}.  Formally this can be proven as follows:
{{quote|Prove that <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>

: <math>\begin{align}
&\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
\le {} &( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0 )
\end{align}</math>

Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]
<br /><br />
<math>\begin{align}
&T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k\\
= {} &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
\end{align}</math>
<br /><br />
Therefore <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0 \text{ for } c = 12k, n_0 = 1</math>
}}

A more [[elegance|elegant]] approach to analyzing this algorithm would be to declare that [''T''<sub>1</sub>..''T''<sub>7</sub>] are all equal to one unit of time, in a system of units chosen so that one unit is greater than or equal to the actual times for these steps.  This would mean that the algorithm's run-time breaks down as follows:<ref>This approach, unlike the above approach, neglects the constant time consumed by the loop tests which terminate their respective loops, but it is [[Trivial (mathematics)|trivial]] to prove that such omission does not affect the final result</ref>
{{quote|<math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \ (\text{for } n \ge 1) =O(n^2).</math>}}

===Growth rate analysis of other resources===
The methodology of run-time analysis can also be utilized for predicting other growth rates, such as consumption of [[DSPACE|memory space]].  As an example, consider the following pseudocode which manages and reallocates memory usage by a program based on the size of a [[computer file|file]] which that program manages:

 '''while''' ''file is still open:''
     '''let''' n = ''size of file''
     '''for''' ''every 100,000 [[kilobyte]]s of increase in file size''
         ''double the amount of memory reserved''

In this instance, as the file size n increases, memory will be consumed at an [[exponential growth]] rate, which is order {{math|''O''(2<sup>''n''</sup>)}}. This is an extremely rapid and most likely unmanageable growth rate for consumption of memory [[Resource (computer science)|resources]].