In college I was first introduced to this definition for algorithm:
An algorithm is a defined process for getting something done. Algorithms are all around us. Recipes are common algorithms. Driving directions can be algorithms. Your morning routine might be an algorithm. How we do the things we do can often, but not always, be described as an algorithm.
In the study of algorithms, we often consider the analysis of how a process scales. That is, as inputs to the process grow to incredibly large sizes, we ask and answer the question: "What factors dominate in determining the cost, both in time and resources, of this process?" The answers to this question often take the form of common mathematical growth functions shown in the diagram below:
As you move across the x-axis you can see that each of these functions grows or increases along the y-axis. While they all grow, they do so at different rates. For example, the linear growth rate is greater than the logarithmic growth rate. In fact you can visually compare each of these curves rather easily for these small values of x, but doing this visual comparison for small values isn't where algorithm analysis normally starts. Remember the point of all this is to answer the question, "But how does it scale?" or "For very large inputs (values of x), which function increases the least?" If an algorithm's representative growth function can scale well, there's profit to be made.
As you can see, the cost of this algorithm grows rapidly. With only 35 items to sort, this Bubble sort machine would cost you well over $1,000 to do the work! You might recognize this graph; it is the graph of an n2 function. Any algorithm that grows its cost in a way that follows the general form of an n2 function we call an n2 algorithm.
The "cost" of an algorithm depends on what you count. In the previous example we counted dollars spent on sorting the items. For computer algorithms the costs normally counted are space and time. Time measures how long the algorithm takes to complete as the number of items increases. Space measures how much extra memory or disk space is needed to complete the algorithm. In other fields, an algorithm's "cost" might refer to other things like money, people required or even distance traveled.
There are only a handful of general functions that are used to represent an algorithm's cost. Here they are:
|n log n||"n-log-n"|
It is important to note with these functions that when the number of items to process is very small, the cost difference is also relatively small. For example, consider the relative cost of processing 5 items using different algorithms, each with a different efficiency type or class. Of course, the dollar costs shown below are fictional, but it should help you compare the different kinds of algorithms. The cost difference between each class of function follows:
|Class||Name||Cost for 5 items|
|n log n||"n-log-n"||$3.49|
This table orders the function types from least expensive to most expensive at large-scale, that is, when the number of items to process is much larger than five. Even so, some of the more costly functions (Exponential for example) are actually cheaper when considered for only 5 items. Normally, algorithm analysis ignores cost at small-scale and looks at what the relative costs are when things get really, really big. Let's look at 1 million items. That's a big number, and for most people, if they sell or work with 1 million things, that qualifies as a large-scale system.
At large-scale, this kind of analysis begins to make sense. With 1 million things to process, you can really see how the order of growth changes dramatically. If you were responsible for a manufacturing plant and had a process whose cost function was an n2 function and you were able to change the process to something that cost more along the lines of a "n-log-n" function, well, you'd have a competitive advantage of $999,994,000,000! That is probably enough to get you that next promotion!
Taking the time to look at your processes, or algorithms, and improving them can result in amazing economic benefits when you are working with large-scale systems. Small changes, even seemingly simple modifications in a core or costly work process can add up to huge economic returns.
What we've been discussing has a name and it is called: asymptotic complexity analysis. It's called this because as an algorithm approaches very large inputs, the cost graph "looks like" or "asymptotically approaches" one of the key functions mentioned above. For our purposes, the word complexity simply means cost.
What does this asymptotic complexity analysis have to do with Economics? Consider this definition for Economics:
Algorithms can optimize production, distribution and consumption, and these advancements can save time and money and drive economic growth. There are large economic incentives to scale up your business and reap the rewards that come with increased size and algorithms can help you do this. Remember, algorithms define how you do what you do, and at large-scale, they really matter. The following examples should better illustrate the value of algorithms in production, distribution and consumption of goods and services.
For years the US Constitution has protected manufacturing algorithms in the form of process patents. These limited monopolies began with these lines in the Constitution:
The constitutional patent protection has been further clarified as follows:
The ability to secure a process patent for exclusive use has obvious economic value. If you are able to discover and patent a new, more effective process for producing a chemical, drug or other material, the process patent offers a legal protection for your algorithmic advantage. It is for this and other reasons that capturing process patents offer a significant financial incentive.
To summarize there are at least three key ways algorithms have a significant impact on economic production:
- Better algorithms can lower production costs
- Better algorithms can allow production to scale
- Better algorithms patented can provide a competitive advantage
As companies deal with market pressures, algorithms-their discovery, improvement and protection-are an important part of doing business.
When we think of the distribution of goods, images of trucks, trains, boats and planes crisscrossing the globe often come to mind. Certainly when you attempt to achieve large-scale distribution, the need to move goods across the globe becomes important. This kind of physical distribution is critical to many economic activities.
Overnight delivery services were largely unknown before the birth of FedEx. Yet it was an insight and an algorithm and its application to shipping that led FedEx to become a synonym for next day delivery. In his autobiographical account of starting up FedEx, Fred Smith explains how the algorithm he chose for distribution was central to his initial design for the company:
When it comes to distribution systems on a large-scale, the development and choice of algorithms have not only an economic impact, but an environmental one as well.
It's hard to imagine now, but it wasn't long ago that searching for and gathering information involved travel, visiting libraries and other institutional records facilities. Google has changed all that, and at the heart of that change was an algorithm, namely PageRank.
This one algorithm solved a real problem: finding relevant information when faced with the information overload online. Word spread fast and soon almost everyone was going to Google to search the web. This presented an opportunity to sell contextual and relevant ads along with the search results and the rest is, as they say, history.
In Google's case, the PageRank algorithm is perhaps one of the most useful and lucrative algorithms in recent history, but it has not come without challenges. Google has had to constantly combat those who try to game the system for profit, using the fact that a system based on an algorithm, even a "smart" one, has inherent and repeatable weaknesses.
Clearly, Google's success shows that creation of a new algorithm for doing something that scales can be a critical part to business. Still, that was not enough. Google has had to continually adapt the algorithm to changes in the market. Perhaps this simply underscores the fact that the people who can invent, maintain and improve these algorithms are even more economically valuable than the algorithms themselves.
The Dark Side of Algorithms
"Not everything that can be counted counts, and not everything that counts can be counted." - Albert Einstein28
One of the great things about an algorithm is the fact that it is an "unambiguous sequence of instructions." This unambiguous nature allows for repeatability and scalability, but this very strength is also a weakness. Process patents, desirable as they are, often specify in clear terms what it means to follow the process and what it means to do something different and thereby avoid infringing on the patent. Since patents are public, you are in a sense giving the competition the map to the minefield! The other and perhaps larger weakness with algorithms is that there are qualities like style, judgment, understanding and creativity that simply resist being defined algorithmically.
Clearly employing repeatable and scalable processes to produce, distribute and consume goods and services is a boon economically, but there is a dark side to this specification and reduction of all things into a "sequence of unambiguous instructions for solving a problem."
The quality of food isn't just in how it tastes, but also in how it helps us to stay healthy. Large-scale and efficient food production has been helpful in meeting the world's hunger needs, but along with the scale have come other problems. High output factory processes have created new risks for large-scale food-borne illnesses and high yield crops can generate food of decreasing nutritional value.
"The only problem with Microsoft is they just have no taste, they have absolutely no taste, and what that means is - I don't mean that in a small way I mean that in a big way. In the sense that they, they don't think of original ideas and they don't bring much culture into their product" - Steve Jobs, 199632
How does one define in systematic and unambiguous terms what is original, beautiful, stylish, elegant or even culturally valuable? Some things simply resist precise definition. Additionally, there is an economic reality that often good enough is sufficient, especially on a large-scale. One can be remarkably successful without these ambiguous and intangible qualities like beauty and elegance. Certainly Jobs' assertion that Microsoft lacks taste hasn't kept the company from being phenomenally successful. Indeed taking the extra time and money to push your work to the level of art can easily be considered wasted effort from an algorithmic efficiency point of view.
On the other hand consider Steve Jobs assessment of their "system" for developing innovative products:
For a company so often praised for style, beauty, innovation and elegance it's somewhat surprising that Apple doesn't have a system in place to ensure continued success along these lines. The reason for this omission is that creativity, art, style and beauty remain far outside the algorithm's grasp.
Now, algorithms and risk probability models often replace this human factor. Is this better? The answer is complicated, but the underwriting of subprime loans for individuals and institutions that were unable to service the loan may not have occurred except for the powerful force of statistical algorithms and investment models suggesting it was a prudent course. These "bad loans" contributed to the housing bubble and the current US economic climate. We are now in the meltdown of the US residential real estate market and the beginnings of a commercial real estate depression. Perhaps there is room for more human judgment in banking loan decisions. This brings to mind what Warren E. Buffett said about the complex securities engineered by Wall Street mathematicians: "Beware of geeks bearing formulas."
Problems of Scale
Algorithms and Their Limitations
Thinking deeply about the core algorithms in your work can be very productive and help you gain a competitive advantage. Algorithmic complexity analysis can help you find areas where you can improve your economic returns significantly. Many great companies have at their core a collection of algorithms that form the engine of their success.
Algorithmic study makes the most economic sense on a large-scale but don't get caught up in the desire to scale. Sometimes the focus that is provided at small scale can allow you to produce things that would simply be impossible to produce in a large-scale environment. Asymptotic complexity is not everything! You can know how to do something extremely well and not be able to explain it or reproduce it at scale, yet it can still be very valuable. There are many important things that can't be succinctly described in an algorithm and this very fact may be your competitive advantage.
1 Levitin, Anany V. Introduction to the Design and Analysis of Algorithms. 2nd ed. Addison Wesley, 2006. Print. ↩
2 For an introduction to Bubble sort see: Bubble sort. Wikipedia: The Free Encyclopedia. Web. ↩
3 This number is very large. I used the command line tool bc, an arbitrary precision calculator, to calculate it and the result was a number 301,030 digits long! It would take 110 pages just to print this number. ↩
4 This number is very, very large. It's so large, in fact, I'm not sure how to calculate it. ↩
5 Definition of "economics." WordNet. Princeton. Web. ↩
6 "Transcript of the Constitution of the United States - Official." Web. 5 Dec 2009. (see Article 1, section 8, clause 8) ↩
7 "35 U.S.C. 101 Inventions patentable. - Patent Laws." Web. 5 Dec 2009. ↩
8 "BENEFICIATION OF POTASH - Google Patent Search." Web. 5 Dec 2009. ↩
9 Bessen, James, and Michael J. Meurer. Patent Failure: How Judges, Bureaucrats, and Lawyers Put Innovators at Risk. illustrated edition. Princeton University Press, 2008. Print. ↩
10 Ibid. ↩
11 Smith, Fred. "How I Delivered the Goods." Web. 5 Dec 2009. ↩
12 "Online Extra: Fred Smith on the Birth of FedEx." Web. 5 Dec 2009. ↩
13 "Right Turn at the Right Time - UPS Pressroom." Web. 5 Dec 2009. ↩
14 "UPS Fact Sheet - UPS Pressroom." Web. 5 Dec 2009. ↩
15 Right Turn at the Right Time ↩
16 "Corporate Information - Google Milestones." Web. 5 Dec 2009. ↩
17 "PC Magazine: Top 100 Web Sites (Google!)." Web. 5 Dec 2009. ↩
18 For a deeper explanation of the algorithm see the patent: "Method for node ranking in a linked database - Google Patent Search." Web. 5 Dec 2009. ↩
19 "Working Paper SIDL-WP-1997-0072." Web. 5 Dec 2009. ↩
20 "Stanford BackRub Web Project." Web. 5 Dec 2009. ↩
21 Sullivan, Danny "Google Bombs Aren't So Scary - Search Engine Watch (SEW)." Web. 5 Dec 2009. ↩
22 "Official Google Blog: Googlebombing 'failure'." Web. 5 Dec 2009. ↩
23 Co-written with Ryan Moulton and Kendra Carattini. "Official Google Webmaster Central Blog: A quick word about Googlebombs." 25 Jan 2007. Web. 5 Dec 2009. ↩
24 "The Times (UK) Spamming Social Media Sites - Waxy.org." Web. 5 Dec 2009. ↩
25 "Official Google Webmaster Central Blog: Google's SEO Starter Guide." Web. 5 Dec 2009. ↩
26 "Derek Powazek - Spammers, Evildoers, and Opportunists." Web. 5 Dec 2009. ↩
27 "Search Engine Optimization (SEO) - Webmasters/Site owners Help." Web. 5 Dec 2009. ↩
28 Albert Einstein, a US (German-born) physicist (1879-1955). This quote is attributed to him because of sign that he had hanging in his office at Princeton. ↩
29 "(WO/2006/068863) METHOD AND APPARATUS FOR MAKING A SANDWICH." Web. 5 Dec 2009. ↩
30 Roberts, Paul. The End of Food. Reprint. Mariner Books, 2009. Print. ↩
31 Pawlick, Thomas F. The End of Food: How the Food Industry is Destroying Our Food Supply--And What We Can Do About It. 1st ed. Barricade Books, 2006. Print. ↩
32 Sen, Paul. Triumph of the Nerds. Ambrose Video, 2002. Print. Transcript. ↩
33 "The Seed of Apple's Innovation." Web. 12 Oct 2004. ↩
34 Kim, Jane J. "New FICO Credit Score Debuts." wsj.com 29 Jan 2009. Wall Street Journal. Web. 5 Dec 2009. ↩
35 Clark, Kim B. Speech given at a City Club luncheon December 18, 2008 ↩
36 Coy, Peter. "Why Subprime Lenders Are In Trouble." BusinessWeek: TopNews 2 Mar 2007. BusinessWeek. Web. 5 Dec 2009. ↩
37 "Declaration of the Summit on Financial Markets and the World Economy." Web. 5 Dec 2009. ↩
38 Foust, Mara Der Hovanesian, Dean. "Why This Real Estate Bust Is Different." BusinessWeek: Online Magazine 5 Nov 2009. BusinessWeek. Web. 5 Dec 2009. ↩
39 Lohr, Steve. "Like J.P. Morgan, Warren E. Buffett Braves a Crisis." The New York Times 6 Oct 2008. NYTimes.com. Web. 5 Dec 2009. ↩
40 Weiss, David. "Impatience and Design by Counter Example" 6 Nov 2006. Web. 5 Dec 2009. ↩
41 "While Rivals Jockey For Market Share, Apple Bathes In Profits." Web. 5 Dec 2009. ↩
42 Gruber, John. "Daring Fireball: Pound the Quality." Web. 5 Dec 2009. ↩