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:

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) = (a constant c)*n = O(n).

The theoretical analysis predicts the performance of the algorithm. To see how this algorithm performs, we run the code in the program below to obtain the execution time for n = 1000000, 10000000, 100000000, and 100000000.

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++) {
k = k + i + j;
}
}

It is a constant time, c, for executing

k = k + i + j;

The outer loop executes n times. For each iteration in the outer loop, the inner loop is executed n times. Thus, the time complexity for the loop is

T(n) = (a constant c)*n*n = O(n^2)

An algorithm with the O(n^2) time complexity is called a quadratic algorithm and it exhibits a quadratic growth rate. The quadratic algorithm grows quickly as the problem size increases. If you double the input size, the time for the algorithm is quadrupled. Algorithms with a nested loop are often quadratic.

Example 3

Consider the following loop:

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

The outer loop executes n times. For i = 1, 2, c , the inner loop is executed one time, two times, and n times. Thus, the time complexity for the loop is

Example 4

Consider the following loop:

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

The inner loop executes 20 times, and the outer loop n times. Therefore, the time complexity for the loop is

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

Example 5

Consider the following sequences:

for (int j = 1; j <= 10; j++) {
k = k + 4;
}

for (int i = 1; i <= n; i++) {
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 complexity 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

Example 7

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

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

The algorithm takes O(n) time. Without loss of generality, assume n = 2^k. You can improve the algorithm using the following scheme:

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

The algorithm takes O(logn) time. For an arbitrary n, you can revise the algorithm and prove that the complexity is still O(logn).

For simplicity, since 0(logn) = 0(log2n) = 0(logan), the constant base is omitted.

原文链接：Examples: Determining Big O