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

22.3 Examples: Determining Big O
This section gives several examples of determining Big O for repetition, sequence,
and selection statements.
Example 1
Consider the time complexity for the following loop:

Key
Point

for ( int i = 1 ; i <= n; i++) {
k = k + 5 ;
}

It is a constant time, c , for executing

k = k + 5 ;

Since the loop is executed n times, the time complexity for the loop is
T ( n ) O ( n ).

The theoretical analysis predicts the performance of the algorithm. To see how this
algorithm performs, we run the code in Listing 22.1 to obtain the execution time for
n

= (a constant c )* n =

= 1000000, 10000000, 100000000, and 100000000.

L ISTING 22.1

PerformanceTest.java
1 public class PerformanceTest {
2 public static void main(String[] args) {
3 getTime( 1000000 );
4 getTime( 10000000 );
5 getTime( 100000000 );
6 getTime( 1000000000 );
7 }
8
9 public static void getTime ( long n) {
10 long startTime = System.currentTimeMillis();
11 long k = 0 ;
12 for ( int i = 1 ; i <= n; i++) {
13 k = k + 5 ;
14 }
15 long endTime = System.currentTimeMillis();
16 System.out.println( "Execution time for n = " + n
17 + " is " + (endTime - startTime) + " milliseconds" );
18 }
19 }

input size 1000000
input size 10000000
input size 100000000
input size 1000000000

time before execution

time after execution

Execution time for n = 1000000 is 6 milliseconds
Execution time for n = 10000000 is 61 milliseconds
Execution time for n = 100000000 is 610 milliseconds
Execution time for n = 1000000000 is 6048 milliseconds

Our analysis predicts a linear time complexity for this loop. As shown in the sample output,
when the input size increases 10 times, the runtime increases roughly 10 times. The execution
confirms to the prediction.
Example 2
What is the time complexity for the following loop?

for ( int i = 1 ; i <= n; i++) {
for ( int j = 1 ; j <= n; j++) {