Editing Analysis of algorithms (section)

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