Algorithmic Efficiency -- Beating a Dead Horse Faster

In computer science, often the question is not how to solve a problem, but how to solve a problem well. For instance, take the problem of sorting. Many sorting algorithms are well-known; the problem is not to find a way to sort words, but to find a way to efficiently sort words. This article is about understanding how to compare the relative efficiency of algorithms and why it's important to do so.

If it's possible to solve a problem by using a brute force technique, such as trying out all possible combinations of solutions (for instance, sorting a group of words by trying all possible orderings until you find one that is in order), then why is it necessary to find a better approach? The simplest answer is, if you had a fast enough computer, maybe it wouldn't be. But as it stands, we do not have access to computers fast enough. For instance, if you were to try out all possible orderings of 100 words, that would require 100! (100 factorial) orders of words. (Explanation) That's a number with a 158 digits; were you to compute 1,000,000,000 possibilities were second, you would still be left with the need for over 1x10^149 seconds, which is longer than the expected life of the universe. Clearly, having a more efficient algorithm to sort words would be handy; and, of course, there are many that can sort 100 words within the life of the universe.

Before going further, it's important to understand some of the terminology used for measuring algorithmic efficiency. Usually, the efficiency of an algorithm is expressed as how long it runs in relation to its input. For instance, in the above example, we showed how long it would take our naive sorting algorithm to sort a certain number of words. Usually we refer to the length of input as n; so, for the above example, the efficiency is roughly n!. You might have noticed that it's possible to come up with the correct order early on in the attempt -- for instance, if the words are already partially ordered, it's unlikely that the algorithm would have to try all n! combinations. Often we refer to the average efficiency, would would be in this case n!/2. But because the division by two is nearly insignificant as n grows larger (half of 2 billion is, for instance, still a very large number), we usually ignore constant terms (unless the constant term is zero).

Now that we can describe any algorithm's efficiency in terms of its input length (assuming we know how to compute the efficiency), we can compare algorithms based on their "order". Here, "order" refers to the mathematical method used to compare the efficiency -- for instance, n^2 is "order of n squared," and n! is "order of n factorial." It should be obvious that an order of n^2 algorithm is much less efficient than an algorithm of order n. But not all orders are polynomial -- we've already seen n!, and some are order of log n, or order 2^n.

Often times, order is abbreviated with a capital O: for instance, O(n^2). This notation, known as big-O notation, is a typical way of describing algorithmic efficiency; note that big-O notation typically does not call for inclusion of constants. Also, if you are determining the order of an algorithm and the order turns out to be the sum of several terms, you will typically express the efficiency as only the term with the highest order. For instance, if you have an algorithm with efficiency n^2 + n, then it is an algorithm of order O(n^2).

Algorithmic Efficiency -- Analyzing Algorithms

The ability to analyze a piece of code or an algorithm and understand its efficiency is vital for understanding computer science.

One approach to determining an algorithm's order is to start out assuming an order of O(1), an algorithm that doesn't do anything and immediately terminates no matter what the input. Then, find the section of code that you expect to have the highest order. From there, work out the algorithmic efficiency from the outside in -- figure out the efficiency of the outer loop or recursive portion of the code, then find the efficiency of the inner code; the total efficiency is the efficiency of each layer of code multiplied together.

For instance, to compute the efficiency of a simple selection sort

	for(int x=0; x	{

	  int min = x;

	  for(int y=x; y	  {

		if(array[y]		  min=y;

	  }

	  int temp = array[x];

	  array[x] = array[min];

	  array[min] = temp;

	}

We compute that the order of the outer loop (for(int x = 0; ..)) is O(n); then, we compute that the order of the inner loop is roughly O(n). Note that even though its efficiency varies based on the value of x, the average efficiency is n/2, and we ignore the constant, so it's O(n). After multiplying together the order of the outer and the inner loop, we have O(n^2).

In order to use this approach effectively, you have to be able to deduce the order of the various steps of the algorithm. And you won't always have a piece of code to look at; sometimes you may want to just discuss a concept and determine its order. Some efficiencies are more important than others in computer science, and on the next page, you'll see a list of the most important and useful orders of efficiency, along with examples of algorithms having that efficiency.

Algorithmic Efficiency -- Various Orders and Example

elow, I will list some of the common orders and give example algorithms.

O(1)

An algorithm that runs the same no matter what the input. For instance, an algorithm that always returns the same value regardless of input could be considered an algorithm of efficiency O(1).

O(logn)

Algorithms based on binary trees are often O(logn). This is because a perfectly balanced binary search tree has logn layers, and to search for any element in a binary search tree requires traversing a single node on each layer.

The binary search algorithm is another example of a O(log n) algorithm. In a binary search, one is searching through an ordered array and, beginning in the middle of the remaining space to be searched, whether to search the top or the bottom half. You can divide the array in half only logn times before you reach a single element, which is the element being searched for, assuming it is in the array.

O(n)

Algorithms of efficiency n require only one pass over an entire input. For instance, a linear search algorithm, which searches an array by checking each element in turn, is O(n). Often, accessing an element in a linked list is O(n) because linked lists do not support random access.

O(nlogn)

Often, good sorting algorithms are roughly O(nlogn). An example of an algorithm with this efficiency is merge sort, which breaks up an array into two halves, sorts those two halves by recursively calling itself on them, and then merging the result back into a single array. Because it splits the array in half each time, the outer loop has an efficiency of logn, and for each "level" of the array that has been split up (when the array is in two halves, then in quarters, and so forth), it will have to merge together all of the elements, an operations that has order of n.

O(n^2)

A fairly reasonable efficiency, still in the polynomial time range, the typical examples for this order come from sorting algorithms, such as the selection sort example on the previous page.

O(2^n)

The most important non-polynomial efficiency is this exponential time increase. Many important problems can only be solved by algorithms with this (or worse) efficiency. One example is factoring large numbers expressed in binary; the only known way is by trial and error, and a naive approach would involve dividing every number less than the number being factored into that number until one divided in evenly. For every increase of a single digit, it would require twice as many tests.