December 2009 Archives

In college I was first introduced to this definition for algorithm:

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.¹

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.

For example, below is a basic chart of possibly the worst of all algorithms for sorting a list of items, namely, Bubble sort.² Imagine a machine you pay to sort items using Bubble sort. The amount you'll have to pay depends on the number of items you ask the machine to sort. The x-axis shows the number of items to sort and the y-axis shows what it will cost, in dollars.

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 n² function. Any algorithm that grows its cost in a way that follows the general form of an n² function we call an n² 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:

Class	Name
1	Constant
log n	Logarithmic
n	Linear
n log n	"n-log-n"
n2	Quadratic
n3	Cubic
2n	Exponential
n!	Factorial

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
1	Constant	$1.00
log n	Logarithmic	$0.70
n	Linear	$5.00
n log n	"n-log-n"	$3.49
n2	Quadratic	$25.00
n3	Cubic	$125.00
2n	Exponential	$32.00
n!	Factorial	$120.00

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.

Class	Name	Cost for 1,000,000 items
1	Constant	$1.00
log n	Logarithmic	$6.00
n	Linear	$1,000,000
n log n	"n-log-n"	$6,000,000
n2	Quadratic	$1,000,000,000,000
n3	Cubic	$1,000,000,000,000,000,000
2n	Exponential	Too large to include!3
n!	Factorial	Much too large to include!4

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 n² 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.

Economics

What does this asymptotic complexity analysis have to do with Economics? Consider this definition for Economics:

Economics: the branch of social science that deals with the production and distribution and consumption of goods and services and their management.⁵

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.

Production

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 Congress shall have Power ... To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries;"⁶

The constitutional patent protection has been further clarified as follows:

"Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement therefore, may obtain a patent therefore."⁷

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.

The patent protection of algorithms is not new. The first patent for a chemical process was granted in 1793 for a process used to make potash.⁸ Since then many famous chemical processes have been patented.⁹

While there are those who criticize the patent system, even some of the most ardent opponents of the current system have concluded "the patent system still appeared to offer positive innovation incentives for drug and chemical firms."¹⁰

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.

Distribution

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:

"My solution was to create a delivery system that operates essentially the way a bank clearinghouse does: Put all points on a network and connect them through a central hub. If you take any individual transaction, that kind of system seems absurd-it means making at least one extra stop. But if you look at the network as a whole, it's an efficient way to create an enormous number of connections. If, for instance, you want to connect 100 markets with one another and if you do it all with direct point-to-point deliveries, it will take 100 times 99-or 9,900-direct deliveries. But if you go through a single clearinghouse system, it will take at most 100 deliveries. So you're looking at a system that is about 100 times as efficient."¹¹

The insight was the growing need to transport goods reliably overnight and the algorithm was this "spoke and hub" delivery system. The algorithm was not new, in fact Delta was already using it when FedEx was in its infancy, but it's application to shipping and next day delivery was new.¹² For FedEx this algorithm served as their initial economic advantage.

Another example of algorithms and distribution improvements comes from UPS and their Right Turn Policy.¹³ UPS has always tried to optimize their delivery routes, but in 2005 UPS began the process of creating a new computerized route optimization system. This new system was in essence an algorithm that allowed for faster delivery of more packages while reducing costs. The new system generates delivery routes that do all they can to avoid left turns and the idling and waiting that accompany them. Ninety percent of the time, if a UPS truck is turning, it's turning right. For a company that delivers 15.8 million packages and documents around the world each day with a fleet of almost 100,000 cars, vans, tractors and motorcycles, this algorithmic improvement adds up.¹⁴

What have been the results of this optimization? In 2007 the algorithm removed 30 million miles off its delivery routes, saved 3 million gallons of gas, and reduce CO2 emissions by 32,000 metric tons, equal to removing 5,300 passenger cars from the road for an entire year.¹⁵

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.

Consumption

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.

It all began at Stanford in 1995. Larry Page and Sergey Brin met while Page was considering attending Stanford for his graduate degree.¹⁶ Part of their research was focused on a "web crawler" that would visit every web page it could find and begin to analyze the page and it's relative importance. The algorithm for determining a page's rank ultimately received the creative name of PageRank. By 1998 PC Magazine reported that Google "has an uncanny knack for returning extremely relevant results."¹⁷

How did this algorithm work?¹⁸ At the most basic level it would create a "citation graph" of the World Wide Web. Pages with more citations or links to it would be given a higher page rank. This idea was not new, but using web links and other web meta data and applying it to cataloging and judging the vast and growing data online was something new indeed.¹⁹

By August 1996, this research project part of the Digital Library Project in the Computer Science Department at Stanford had discovered roughly 75 million pages on the Internet and indexed about 30 million of them in a 28 GB database! It was obvious that the Google algorithm would need to be something that could deal with scale. This algorithm would need to deal with enormous amounts of data while still allowing instantaneous access to a constantly changing data set.²⁰

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.

Googlebombing is when a person or group tricks Google's algorithm to return a certain search result. Since at least 1999 people have attempted to influence the ranking of particular pages in the search results returned by Google. My first experience with googlebombing was when I was informed that the top result for the search "more evil than Satan himself" was a link to Microsoft's web page.²¹ Google resisted manually tweaking these results citing the importance of the "objectivity" of the algorithm.²² In 2007 Google changed the algorithm so that this kind of thing was more difficult,²³ but the economic incentive to be on the first page of Google's search results has continued to motivate determined hackers and business people alike.²⁴ Search Engine Optimization (SEO) is the process of changing your website's data to improve rank and relevance in the Google search results.²⁵ While there are legitimate ways to improve your rank, significant effort has been invested in finding ways to illegitimately place their website on the first page or top spot in the search results.²⁶ Additionally Search Engine Optimization scams are prevalent. It is common for a business to pay a purported SEO company for a better page rank, often with little success.²⁷

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 Einstein²⁸

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."

Food

Consider your personal experience with food. Have you noticed a difference between homemade meals and those produced at a fast food establishment? If you have, you probably haven't noticed that the fast food was better. McDonalds famously applied for a patent with a 55-page description of a "Method and Apparatus for Making a Sandwich" underscoring their algorithmic focus to food production.²⁹ While much of what has made McDonalds successful has been their focus on algorithmic repeatability, this has allowed for worldwide growth in scale, not deep improvements in culinary quality.

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 Unquantifiable

"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, 1996³²

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:

The system is that there is no system. That doesn't mean we don't have process. Apple is a very disciplined company, and we have great processes. But that's not what it's about. Process makes you more efficient.

But innovation comes from people meeting up in the hallways or calling each other at 10:30 at night with a new idea, or because they realized something that shoots holes in how we've been thinking about a problem. It's ad hoc meetings of six people called by someone who thinks he has figured out the coolest new thing ever and who wants to know what other people think of his idea.³³

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.

Banking

Perhaps nothing is more central to our economic system than banking. As banking operations have become more sophisticated and computer automated, the use of algorithms to make important decisions has increased.³⁴

In the past, getting a loan meant a personal visit to a loan officer of a bank and an interview. Following the interview and documented analysis of income, the loan officer would discuss the loan with a loan approval committee and make the case for issuing the loan.³⁵

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

One reason to focus energy on algorithms comes from the problems associated with scale. When you grow the raw size of an organization or the customers you serve, algorithms can help you deal with that growth in a uniform way. On the other hand, this very growth can make it hard to focus. The reason that focus is often lost at scale is that a small percentage of a big number is still a big number! Even small problems are big problems when magnified by the sheer size of things. Focused efforts become more defuse, as almost any effort pales in comparison to the magnitude of the overall size of things. In this case, one's focus on size, algorithms and their efficiency are of utmost importance, but this comes at the cost of a host of smaller advancements which can be the seeds of real innovation.⁴⁰

Sometimes limiting growth can help generate profit as you focus on quality or target your product effectively. Apple has done this recently with the iPhone. While many have suggested that Apple should focus on capturing market share, Apple has been focusing on profit-share. According to a recent report, Apple made $1.6 billion in operating profit off of the iPhone in Q3 2009. In the same quarter Nokia, made $1.1 billion, but consider this: Apple owns 2.5% of the cell phone market while Nokia controls about 35% of the market! Apple's focus is on a smaller sector of the market, but a sector where they can be focused and extremely profitable.⁴¹

Apple doesn't always play only for profit share. Certainly the iTunes Music Store is a market share leader, but there is something to be learned from growth through focus rather than scale. Apple's own iPhone App Store provides another example of large-scale and the challenges of "quality vs. quantity" that often come with it.⁴²

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.

References

¹ Levitin, Anany V. Introduction to the Design and Analysis of Algorithms. 2nd ed. Addison Wesley, 2006. Print. ↩

² For an introduction to Bubble sort see: Bubble sort. Wikipedia: The Free Encyclopedia. Web. ↩

³ 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. ↩

⁴ This number is very, very large. It's so large, in fact, I'm not sure how to calculate it. ↩

⁵ Definition of "economics." WordNet. Princeton. Web. ↩

⁶ "Transcript of the Constitution of the United States - Official." Web. 5 Dec 2009. (see Article 1, section 8, clause 8) ↩

⁷ "35 U.S.C. 101 Inventions patentable. - Patent Laws." Web. 5 Dec 2009. ↩

⁸ "BENEFICIATION OF POTASH - Google Patent Search." Web. 5 Dec 2009. ↩

⁹ Bessen, James, and Michael J. Meurer. Patent Failure: How Judges, Bureaucrats, and Lawyers Put Innovators at Risk. illustrated edition. Princeton University Press, 2008. Print. ↩

¹⁰ Ibid. ↩

¹¹ Smith, Fred. "How I Delivered the Goods." Web. 5 Dec 2009. ↩

¹² "Online Extra: Fred Smith on the Birth of FedEx." Web. 5 Dec 2009. ↩

¹³ "Right Turn at the Right Time - UPS Pressroom." Web. 5 Dec 2009. ↩

¹⁴ "UPS Fact Sheet - UPS Pressroom." Web. 5 Dec 2009. ↩

¹⁵ Right Turn at the Right Time ↩

¹⁶ "Corporate Information - Google Milestones." Web. 5 Dec 2009. ↩

¹⁷ "PC Magazine: Top 100 Web Sites (Google!)." Web. 5 Dec 2009. ↩

¹⁸ 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. ↩

¹⁹ "Working Paper SIDL-WP-1997-0072." Web. 5 Dec 2009. ↩

²⁰ "Stanford BackRub Web Project." Web. 5 Dec 2009. ↩

²¹ Sullivan, Danny "Google Bombs Aren't So Scary - Search Engine Watch (SEW)." Web. 5 Dec 2009. ↩

²² "Official Google Blog: Googlebombing 'failure'." Web. 5 Dec 2009. ↩

²³ 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. ↩

²⁴ "The Times (UK) Spamming Social Media Sites - Waxy.org." Web. 5 Dec 2009. ↩

²⁵ "Official Google Webmaster Central Blog: Google's SEO Starter Guide." Web. 5 Dec 2009. ↩

²⁶ "Derek Powazek - Spammers, Evildoers, and Opportunists." Web. 5 Dec 2009. ↩

²⁷ "Search Engine Optimization (SEO) - Webmasters/Site owners Help." Web. 5 Dec 2009. ↩

²⁸ 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. ↩

²⁹ "(WO/2006/068863) METHOD AND APPARATUS FOR MAKING A SANDWICH." Web. 5 Dec 2009. ↩

³⁰ Roberts, Paul. The End of Food. Reprint. Mariner Books, 2009. Print. ↩

³¹ 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. ↩

³² Sen, Paul. Triumph of the Nerds. Ambrose Video, 2002. Print. Transcript. ↩

³³ "The Seed of Apple's Innovation." Web. 12 Oct 2004. ↩

³⁴ Kim, Jane J. "New FICO Credit Score Debuts." wsj.com 29 Jan 2009. Wall Street Journal. Web. 5 Dec 2009. ↩

³⁵ Clark, Kim B. Speech given at a City Club luncheon December 18, 2008 ↩

³⁶ Coy, Peter. "Why Subprime Lenders Are In Trouble." BusinessWeek: TopNews 2 Mar 2007. BusinessWeek. Web. 5 Dec 2009. ↩

³⁷ "Declaration of the Summit on Financial Markets and the World Economy." Web. 5 Dec 2009. ↩

³⁸ Foust, Mara Der Hovanesian, Dean. "Why This Real Estate Bust Is Different." BusinessWeek: Online Magazine 5 Nov 2009. BusinessWeek. Web. 5 Dec 2009. ↩

³⁹ 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. ↩

⁴⁰ Weiss, David. "Impatience and Design by Counter Example" 6 Nov 2006. Web. 5 Dec 2009. ↩

⁴¹ "While Rivals Jockey For Market Share, Apple Bathes In Profits." Web. 5 Dec 2009. ↩

⁴² Gruber, John. "Daring Fireball: Pound the Quality." Web. 5 Dec 2009. ↩