-
This is an algorithm, seen in line E on the Order of Algorithms graph, in which the number of steps required to solve a problem increases as a function of N2. For example, here is bubbleSort.
void bubbleSort( ArrayList<Comparable> list
)
{
for ( int outer = 0; outer < list.length - 1;
outer++ )
{
for ( int inner = 0; inner < list.size()-outer-1;
inner++ )
{
if (
list.get(inner).compareTo(list.get(inner + 1) > 0 )
{
// swap list[inner] & list[inner+1]
Comparable temp = list.get(inner);
list.set(inner, list.get(inner + 1));
list.set(inner + 1, temp);
}
}
}
}
-
The if
statement is buried inside nested loops, each of which is tied to the size of the data set, N. The if
statement is going to be executed approximately N times for each of N items, or N2 times in all.
-
The efficiency of this bubble sort was slightly improved by having the inner loop decrease, but we still categorize this as a quadratic algorithm.
-
For example, the number of times the inner loop happens varies from 1 to (N-1). On average, the inner loop occurs (N/2) times.
-
The outer loop happens (N-1) times, or rounded off N times.
-
The number of times the if statement is executed is equal to this expression:
# if statements = (Outer loop) * (Inner loop)
# if statements = (N) * (N/2)
# if statements = N2/2
-
The coefficient 1/2 becomes insignificant for large values of N, so we have an algorithm that is quadratic in nature.
-
When determining the order of an algorithm, we are only concerned with its category, not a detailed analysis of the number of steps.