|
|
|
| |
|
|
|
|
By itself, the inner loop performs S2* L steps, but because it is repeated N times by the outer loop, it accounts for a total of S2* L * N steps. If L is a constant, then the algorithm still executes in linear time. |
|
|
|
| |
|
|
|
|
Now, suppose that for each of the N outer loop iterations, the inner loop performs N steps (L = N). Here the formula for the total steps is |
|
|
|
| | | | |
|
|
|
|
Because N2 grows much faster than N (for large values of N), the inner loop term (S2 * N2) accounts for the majority of steps executed and the work done. So the corresponding execution time is essentially proportional to N2. If we have a doubly nested loop, where each loop depends on N, then the expression is |
|
|
|
| |
|
|
|
|
(S3*N3)+(S2*N2)+(S1*N)+S0 |
|
|
|
| |
|
|
|
|
and the work and time are proportional to N3whenever N is reasonably large. |
|
|
|
| |
|
|
|
|
The table below shows the number of steps required for each increase in the exponent of N. |
|
|
|
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
|
|
|
|
As you can see, each time the exponent increases by 1, the number of steps is multiplied by an additional order of magnitude (factor of 10). That is, if N is made 10 times greater, the work involved in an N2 algorithm increases by a factor of 100, and the work involved in an N3 algorithm increases by a factor of 1000. To put this in more concrete terms, an algorithm with a doubly nested loop, in which each loop depends on the number of data values, takes 1000 steps for 10 input values and 1 trillion steps for 10,000 values. On a computer that executes 1 million instructions per second, the latter case would take more than 11 days to run. |
|
|
|
| |
|
|
|
|
The table also shows that the steps outside of the innermost loop account for an insignificant portion of the total number of steps as N gets bigger. Because the innermost |
|
|
|
|
|
|
|
|
|
|
(text box continues on next page) |
|
|
|
|
|
