Good, Motivating Examples for Algorithmic Complexity

Question

I was recently reading a really good article on this topic, and I realize that it could be a very good added value for students to understand better and appreciate (and eventually put in practice) all the theory that is behind Algorithm Complexity¹. Certainly, not everyone will apply this in the future, since the most efficient way to solve a problem is not always required (although it should be). I think more people should be interested in this, since it has benefits in various ways.

To understand my question a little bit better, I want to give an example of my own personal experience.

From the very first moment I learned about Trees and Binary Trees (a long time ago), I don't know why, I hate them. I never thought about them like a solution to the many problems I had to face and resolve. Some time ago, I was told to recreate from scratch the Shannon–Fano encoding as an exercise. I enjoyed that so much! And of course, for that encoding, everything is based on trees. It was at that point that I was more interested in trees, how they work and their functionality to solve real life problems.

So, in the same way the Shannon–Fano coding help me to understand better and made me want to go deeper in the tree's data structure theory, I'm asking for good motivating examples that might help others understand and want to learn more about Algorithm Complexity.

---

¹ Just to clarify, when I say Algorithm Complexity, I'm talking about all the theory and techniques that are available to know how efficient an algorithm is, and to compare that information with other results, thus leading to the most efficient way to solve a problem.

Answer 1

I attack this problem with three "visits" over the course of two years with my students

1. At our first brush with Complexity, I don't spend a ton of time motivating the study of it. I introduce the notations of $\Omega$, $\Theta$, and $O$ (as well as briefly touching upon $\omega$, $\theta$, and $o$). I show the difference between linear and binary search, and then explore four sorting algorithms: bubble, selection, insertion, and bogosort. (This is fairly early on in the curriculum, and we haven't dealt with recursion yet, so I skip out on quicksort and mergesort.) The last one makes them laugh, and makes the material at least have a point: some algorithms are just worse than others.
2. Later in the year, we look at quicksort and mergesort. At this point, again, we use this only as a chance to review the concepts and the notation.

3. Near the beginning of the second year, I talk about why algorithmic study matters. Computers get insanely faster over time, right? (See Richard's answer for some eyebrow-raising numbers). Since our computers are getting faster, it only stands to reason that things that are slow to compute today will also just get faster.

   "Au contraire!" I cry, "as our computers get faster, our algorithms are getting slower, you see!" What do I mean by this outrageous claim? As our computers get faster, our hard drives also get bigger. By necessity, we perform calculations with larger and larger data sets.

   So, let's use high-end rendering as an example. In 1980, Apple came out with the Apple III computer, which shipped with a whopping 5 megabytes of diskspace. It also used the 6502B processor. It could perform about 0.43 million instructions per second (MIPS). Today, hard drives come in at about 6 gigabytes, and 305 billion instructions per second. My numbers don't have to be exact to make this work, though.

   If we processed a complex graphic that took about .5% of our hard drive using a $O(n^3)$ algorithm in 1980, that would be about 2,500 bytes of data, and it would take us roughly 9.25 years to complete. That's awful!! But if we did that today, (roughly 30 megabytes and 305 billion computations per second), it would take us over 28 thousand years to complete. We're trending the wrong way! The problem is that, even at a relatively cheap function like $O(n^3)$, the growth due to data creep is just far faster than Moore's Law. Faster computers can't deal with correspondingly bigger problems if the $O$ sucks.

4. Finally, a few weeks later, I talk in grand, futuristic terms about the Big Picture. This is more to excite their curiosity than anything else. The three drivers of possibility with computers are, I argue, smaller transistors, better battery life, and better algorithms. If you take a $O(n^3)$ algorithm and find a way to accomplish a similar task in $n^2$ time, that's a foundational enabler. You don't become individually famous, but you change the world. The Google Maps team didn't solve the Traveling Salesman problem, they developed algorithms that could get likely best answers without the guarantee. The bottom line is that developing algorithms with better complexity literally enables us to do new things on practical timescales. To paraphrase Heroes, change the algorithm, change the world.

Answer 2

How badly written software can undo 120 years of computer hardware improvements.

First blow their minds with Moore's law: 120 years of progress from mechanical devices to the present day, there has been a $2^{60}$ improvement.

Then show them how easy it is to lose all of this hard won, performance, improvement (in the hardware), by using poor software algorithms: If we are searching through a sorted list of $2^{30} \approx 10^9$ nodes, using liner search ($O(n)$), then we have the performance of $60$ year old computer, doing it the smart way (binary search($O(log n)$)). Even $2^{20} \approx 10^6$ nodes, is $40$ years of progress lost.

Therefore if we want to see the benefit of hardware improvement, we need to not waste it. Also Moore's law will come to an end soon (as is true for all exponential growth. It is also true that most people will deny this, citing that it has not happened yet as evidence, until a short time after it happens).