Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 784

• Accessing or modifying an individual element of an array

• Simple method calls (where the method does not perform a loop)

One kind of variable that does not require a fixed amount of time to initialize is an
array. When an array is constructed, Java zeroes each array element, which takes
more time for longer arrays. Some types of objects also have lengthy code in their
constructors that makes them take longer to construct.
From the preceding simple rules, we can extrapolate the runtimes of larger and
more complex pieces of code. For example, the runtime of a group of statements in
sequential order is the sum of the individual runtimes of the statements:

statement1.
statement2.
statement3.

3

The runtime of a loop is roughly equal to the runtime of its body times the number
of iterations of the loop. For example, a loop with a body that contains K simple
statements and that repeats N times will have a runtime of roughly ( K * N ):

for (N times) {
statement1.
statement2.
statement3.
}

3N

The runtime of multiple loops placed sequentially (not nested) with other state-
ments is the sum of the loops' runtimes and the other statements' runtimes:

statement1.
for (N times) {
statement2.
}

N

M + N + 3

for (M times) {
statement3.
}
statement4.
statement5.

M

The runtime of a loop containing a nested loop is roughly equal to the runtime of
the inner loop multiplied by the number of repetitions of the outer loop:

for (M times) {
for (N times) {
statement1.
statement2.
statement3.
}
}

3 3N 3MN