Changes

==Computational Complexity==

==Computational Complexity==

One aspect of algorithms implemented in computer programs is that of computational complexity, which denotes how efficient (fast) they are.  Asymptotic Notation is the formal means of describing the running time of an algorithm and the size of its inputs.<ref>Introduction to Computation and Programming Using Python by John V. Guttag</ref>  The most commonly used notation is called "Big O", which is used to give an upper bound on the computational complexity of the routine.  Some examples:

One aspect of algorithms implemented in computer programs is that of computational complexity, which denotes how efficient (fast) they are.  Asymptotic Notation is the formal means of describing the running time of an algorithm and the size of its inputs.<ref>John V. Guttag, <i>Introduction to Computation and Programming Using Python</i> (MIT Press:2016)</ref>  The most commonly used notation is called "Big O", which is used to give an upper bound on the computational complexity of the routine.  Some examples:

<ul>

<ul>

<li><b>O(1)</b> indicates constant running time.</li>

<li><b>O(1)</b> indicates constant running time.</li>

<li><b>O(n)</b> indicates running time that is linear with the size of the inputs.</li>

<li><b>O(n)</b> indicates running time that is linear with the size of the inputs.</li>

<li><b>O(log n)</b> indicates running time that is logarithmic.</li>

<li><b>O(log n)</b> indicates running time that is logarithmic.</li>

<li><b>O(n<sup2>k</sup>)</b> indicates polynomial running time.  For instance, O(n²) indicates that the algorithm is quadratic - that the running time increases as the square of the size of the input.</li>

<li><b>O(n^x)</b> indicates polynomial running time.  For instance, O(n²) indicates that the algorithm is quadratic - that the running time increases as the square of the size of the input.</li>

</ul>

</ul>