Understanding Algorithmic Complexity

Understanding Algorithmic Complexity

Algorithmic complexity is a measure of how much computation a program will perform when using a particular algorithm. It is a measure of its efficiency and estimate of operation count. It is not a measure of the complexity of the code necessary to implement a particular algorithm. An algorithm with low algorithmic complexity is likely to be more difficult to implement than an algorithm with higher algorithmic complexity. The most important fact is that the algorithmic complexity is not a model of the execution time but a model of the way execution time changes as the size of the input changes. It is probably best to illustrate this through some examples.

Examples of Algorithmic Complexity

Suppose you want to write a program that sums the first N numbers. You would proba-bly write something like the code shown in Listing 2.1.

Listing 2.1     Sum of the First N Numbers

void sum(int N)

{

int total=0;

for (int i=1; i<=N; i++)

{

total += i;

}

printf( "Sum of first %i integers is %i\n", N, total );

}

For a given input value N, the code will take N trips around the loop and do N additions. The algorithmic complexity focuses on the number of operations, which in this case are the N additions. It assumes that any additional costs are proportional to this number. The time it would take to complete this calculation is some cost per addition, k, multiplied by the number of additions, N. So, the time would be k ∗ N. The algorithmic complexity is a measure of how this time will change as the size of the input changes, so it is quite acceptable to ignore the (constant) scaling factor and say that the calculation will take of the order of N computations. This is typically written O(N). It is a very use-ful measure of the time it will take to complete the program as the size of the input changes. If N is doubled in value, then it will take twice as long for the program to complete.

Another example will probably clarify how this can be useful. Assume that you want to sum the total of the first N factorials (a factorial is N ∗ (N-1) ∗ (N-2) ∗ ... ∗ 1); you might write a program similar to the one shown in Listing 2.2.

Listing 2.2     Sum of the First N Factorials

int factorial(int F)

{

int f = 1;

for (int i=1; i<=F; i++)

{

f = f*i;

}

return f;

}

void fsum(int N)

{

int total = 0;

for (int i=1; i<N; i++)

{

total+=factorial(i);

}

}

This program contains a doubly nested loop. The outer loop will do N iterations, and the inner loop will do an average (over the run) of N/2 iterations. Consequently, there will be about N ∗ N/2 multiply operations and N additions. The algorithmic complex ity is concerned only with the dominant factor, which is N ∗ N. So, the entire calcula-tion is O(N²). If N doubles in size, the time that this algorithm takes will go up by a factor of 4.

The complexity is represented by the dominant term in the function. If the complex-ity turned out to be (N+1)², then as N increased, there would eventually be little differ-ence between this and N². In the limit, as N becomes larger, O(N²) will dominate the complexity of O(N).

The previous examples are somewhat contrived, and in both cases there are more efficient ways to provide the required result.

A more common programming problem is sorting data. The domain of sorting has many different algorithms, of which the two most famous are probably bubble sort and quicksort.

Bubble sort iterates through a list of numbers, comparing adjacent pairs of numbers. If the pair is not in the correct sort order, the pair is swapped. Listing 2.3 shows a simple implementation.

Listing 2.3 Implementation of Bubble Sort

void bubble_sort(int*array, int N)

{

int sorted =0; while ( !sorted )

{

sorted=1;                   

for       ( int i=0; i        < N-1; i++ )

{                                  

if (array[i] >    array[i+1])

{                                  

            int temp          =          array[i+1];

            array[i+1] =    array[i];

            array[i]            =          temp;

            sorted=0;                   

}                                  

}                                  

}

}

The smallest elements “bubble” to the top of the array, which is why it’s called a bub-ble sort. It also leads to the optimization, omitted from this implementation, that it is not necessary to sort the bottom of the list, because it will gradually fill with previously sorted largest elements.

Using the algorithm as written, it will take N comparisons to get each element into the correct place. There are N elements, so it will take N ∗ N comparisons to sort the entire list. For unsorted data, this leads to an algorithmic complexity of O(N²).

On the other hand, quicksort, as might be expected by its name, is a much faster algo-rithm. It relies on splitting the list of elements into two: a list of elements that are smaller than a “pivot” element and elements that are larger. Once the list has been split, the algo-rithm repeats on each of the smaller lists. An implementation of the quicksort algorithm might look like the code shown in Listing 2.4.

Listing 2.4     Implementation of Quicksort

void quick_sort(int * array, int lower, int upper)

{

int tlower = lower int tupper = upper;

while (tlower <= tupper)

{

while ( array[tlower] < pivot ) { tlower++; } while ( array[tupper] > pivot ) { tupper--; } if ( tlower <= tupper )

{

tmp          = array[tlower];

array[tlower] = array[tupper];

array[tupper] = tmp;

tupper--;

tlower++;

}

}

if (lower<tupper) { quick_sort(array,        lower, tupper); }

if (tlower<upper) { quick_sort(array, tlower,   upper); }

}

The algorithmic complexity of quicksort is hard to calculate. For the average case, it is possible to prove that the complexity is O(N∗log₂(N)). This can be explained using the following reasoning. Assume a uniform distribution of items, and that every time the array is split, it will result in two equal halves. For a given N, it will take log₂(N) splits before the array is split into a sequence of N individual elements and the sort is com-plete. Each time the array splits, there are two function calls, one to sort the lower half and one to sort the upper half. So, at every split, the entire array of N elements will be iterated through. Therefore, the algorithmic complexity is O(N∗log₂(N)).

To see the practical impact of this difference in the complexity of sorting operations, consider sorting a list of 10 items. The bubble sort algorithm will perform about 10 ∗ 10 = 100 operations, whereas quicksort will perform about 10 ∗ log₂(10) = 30 operations, which is about three times fewer operations. However, the time taken to sort a 10-element list is unlikely to be a significant factor in the runtime of an application. It is more inter-esting to consider a list of 1,000 elements. The bubble sort will take about 1,000,000 operations, while quicksort will take about 3,000 operations—a ratio of about 300×.