Java Reference
In-Depth Information
we easily see that
n
2
2n log n
= 1
because n grows faster than 2 log n. Thus, n
2
is in (2n log n).
lim
n!1
3.5
Calculating the Running Time for a Program
This section presents the analysis for several simple code fragments.
Example3.9
We begin with an analysis of a simple assignment to an
integer variable.
a=b;
Because the assignment statement takes constant time, it is (1).
Example3.10
Consider a simple
for
loop.
sum=0;
for(i=1;i<=n;i++)
sum+=n;
The first line is (1). The
for
loop is repeated n times. The third
line takes constant time so, by simplifying rule (4) of Section 3.4.4, the
total cost for executing the two lines making up the
for
loop is (n). By
rule (3), the cost of the entire code fragment is also (n).
Example3.11
We now analyze a code fragment with several
for
loops,
some of which are nested.
sum=0;
for(j=1;j<=n;j++) //Firstforloop
for(i=1;i<=j;i++)// isadoubleloop
sum++;
for(k=0;k<n;k++) //Secondforloop
A[k]=k;
This code fragment has three separate statements: the first assignment
statement and the two
for
loops. Again the assignment statement takes
constant time; call it c
1
. The second
for
loop is just like the one in Exam-
ple 3.10 and takes c
2
n = (n) time.
The first
for
loop is a double loop and requires a special technique. We
work from the inside of the loop outward. The expression
sum++
requires
constant time; call it c
3
. Because the inner
for
loop is executed i times, by
