Algorithms | Research & Encyclopedia Articles

Algorithms

An algorithm is a sequence of operations carried out systematically to yield a result in a finite number of steps. An algorithm does not have to be expressed in any particular form or language, and so baking recipes, assembly manuals, computer programs, and street directions can all be considered algorithms.

The word algorithm comes from the name of the ancient Arabian mathematician Mohammed ibn-Musa Al-Khowarizmi, who lived from about 780 to 850. Al-Khowarizmi was born in central Asia in what is now known as Uzbekistan, but he did most of his important work in Baghdad, now in Iraq. He is generally considered to be the father of modern algebra, and he believed that any mathematical problem, now matter how complex, could be solved if it were broken into smaller steps and each step solved in isolation. Modern day computing is fundamentally algorithmic in nature, because computer programs work by carrying out a set of instructions in a predefined sequence. Indeed, from one perspective, Al-Khowarizmi seems to have been quite far-sighted since one common way for improving programs' speed and efficiency is to split the problem into many smaller problems.

Algorithms vary in complexity. Some algorithms, like basic ones for deciding if two character strings are the same, are very simple; but others are extremely complex, like the algorithms for predicting what the experts expect (and hope) will happen in the world's stock markets.

The complexity of an algorithm is often described using what is called "big-O notation." Big-O notation is a theoretical measure of how an algorithm will execute, in terms of the time or computer memory required given the size of the problem itself. The size of the problem is typically measured by the number of items in it.

This measure is extremely important when trying to decide if an algorithm is going to be sufficient to solve a problem of a given size, no matter how much time and money are spent in building computers powerful enough to run it. Often algorithms that are theoretically possible require resources that would bankrupt the nation to implement.

Algorithms are often described as having "linear," "logarithmic," "polynomial," or "exponential" complexity, and in big-O notation these are expressed as O(n), O(log n), O(n^k), and O(kⁿ), where for the last two, "k" is constant. Generally, for a given size of input, linear algorithms, the least complex, complete in the shortest amount of time. Exponential algorithms, the most complex, take the longest, and logarithmic and polynomial algorithms are in the middle, faster to slower.

Algorithmic complexity is at the heart of nearly all computer security matters in the world today. This is because the explosion in the use of computers in financial and other transactions has also seen an explosion in the use of cryptography. Cryptography is the science of using mathematics to keep data secret from people who are not authorized to see it, and in computing that means using large numbers and certain properties they possess.

Nearly all of the commerce on the Internet, for instance, relies upon the simple fact that it is very difficult to discover what two numbers divide a given random number. These two numbers are called the random number's "factors" and the problem of discovering them is called "factoring."

The simplest algorithm would be to start at 2, try and divide the number, and if this were unsuccessful, add 1, try again, and so on. Unfortunately this algorithm is highly exponential and very quickly becomes completely unworkable because modern cryptography uses numbers whose factors are extremely large, of the order of 10⁶⁰⁰ (that's 10 followed by 600 zeros) and even larger. Even the best-known algorithms, which are extremely sophisticated and powerful, are not quick enough to factor numbers of this size during the expected life of this universe--even if they were to run on the fastest computers we can build. This is because even the best algorithms for solving this problem are exponential, and one of the challenges for mathematicians of this century is to determine if there are polynomial solutions to this problem of factoring. Interestingly factoring belongs to a class of problems that are termed NP-complete. Essentially if anyone can find a factoring algorithm that has "polynomial complexity" rather than "exponential complexity" then it means that all other NP-complete problems, such as the "traveling salesman" problem and the "discrete logarithm," also have a polynomial complexity algorithm as a solution. Most mathematicians now believe that NP-complete problems have no such general solution in polynomial time, but there is currently no way of proving this. However, if a polynomial solution ever does emerge, then it will be devastating to the entire global economy--it will mean all previously secure computer systems would be wide open to attack.