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++;