Java Reference
In-Depth Information
simplifying rule (4) it has cost c 3 i. The outer for loop is executed n times,
but each time the cost of the inner loop is different because it costs c 3 i with
i changing each time. You should see that for the first execution of the outer
loop, i is 1. For the second execution of the outer loop, i is 2. Each time
through the outer loop, i becomes one greater, until the last time through
the loop when i = n. Thus, the total cost of the loop is c 3 times the sum of
the integers 1 through n. From Equation 2.1, we know that
n X
i = n(n + 1)
2
;
i=1
which is (n 2 ). By simplifying rule (3), (c 1 + c 2 n + c 3 n 2 ) is simply
(n 2 ).
Example3.12 Compare the asymptotic analysis for the following two
code fragments:
sum1=0;
for(i=1;i<=n;i++) //Firstdoubleloop
for(j=1;j<=n;j++)// dontimes
sum1++;
sum2=0;
for(i=1;i<=n;i++) //Seconddoubleloop
for(j=1;j<=i;j++)// doitimes
sum2++;
In the first double loop, the inner for loop always executes n times.
Because the outer loop executes n times, it should be obvious that the state-
ment sum1++ is executed precisely n 2 times. The second loop is similar
to the one analyzed in the previous example, with cost P j=1 j. This is ap-
proximately 1 2 n 2 . Thus, both double loops cost (n 2 ), though the second
requires about half the time of the first.
Example3.13 Not all doubly nested for loops are (n 2 ). The follow-
ing pair of nested loops illustrates this fact.
sum1=0;
for(k=1;k<=n;k * =2) //Dologntimes
for(j=1;j<=n;j++)//Dontimes
sum1++;
sum2=0;
for(k=1;k<=n;k * =2) //Dologntimes
for(j=1;j<=k;j++)//Doktimes
sum2++;
 
Search WWH ::




Custom Search