DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 826

for ( int j = 1 ; j <= 20 ; j++) {
k = k + i + j;
}
}

The first loop executes 10 times, and the second loop 20 * n times. Thus, the time com-
plexity for the loop is

T ( n ) = 10 * c + 20 * c * n = O ( n )

Example 6
Consider the following selection statement:

if (list.contains(e)) {
System.out.println(e);
}
else
for (Object t: list) {
System.out.println(t);
}

Suppose the list contains n elements. The execution time for list.contains(e) is
O ( n ). The loop in the else clause takes O ( n ) time. Hence, the time complexity for the
entire statement is

T ( n ) = if test time + worst @ case time (if clause, else clause)

= O ( n ) + O ( n ) = O ( n )

Example 7
Consider the computation of a n for an integer n . A simple algorithm would multiply an
times, as follows:

result = 1 ;
for ( int i = 1 ; i <= n; i++)
result *= a;

2 k . You can

The algorithm takes O ( n ) time. Without loss of generality, assume n =

improve the algorithm using the following scheme:

result = a;
for ( int i = 1 ; i <= k; i++)
result = result * result;

The algorithm takes O( log n ) time. For an arbitrary n , you can revise the algorithm and
prove that the complexity is still O( log n ). (See Checkpoint Question 22.7.)

Note
For simplicity, since 0 (log n ) = 0 (log 2 n ) = 0 (log a n ), the constant base is omitted. omit base

22.3

✓ ✓

Count the number of iterations in the following loops.

Check

Point

int count = 1 ;
while (count < 30 ) {
count = count * 2 ;
}

int count = 15 ;
while (count < 30 ) {
count = count * 3 ;
}

(a) (b)