Editing Analysis of algorithms (section)

===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.