How to bring attention to computational complexity?

Question

Many beginners strive to solve given problems, without thinking about efficiency of solution.

Consider such Python code:

data = [int(n) for n in input().split()]
max_el = max(data)

# count multiplicity of every element in data
counting_table = [data.count(i) for i in range(max_el+1)]

This solution seems elegant, but is in fact $O(max(data) \cdot len(data))$, while a solution with $O(len(data))$ is possible.

What heuristics can I teach to detect such code which could be done asymptotically faster? What are the most illustrative examples of how a poorly-crafted algorithm which can't tackle a bit more data than anticipated?

Answer 1

One technique I use for sorting algorithms follows after CS50's demonstrations of the differences among bubble sort, selection sort, and insertion sort. I have 8 students line up in the following order:

4 - 2 - 6 - 8 - 1 - 3 - 7 - 5

Here, 4 represents index 0 of an array of numbers I'd like to sort. I literally walk them through the algorithms, and they can see how much walking I have to do up and down the "array" in order to get it sorted. When it comes time to examine the code for these algorithms, I remark on the use of for loops and how nested for loops lead to $O(n^2)$.

We compare the iterative approach with the recursive approach of merge sort (which certainly could be added to the "walking" demo), which goes back to something we discuss on Day 0 about linear v. binary search. I have students explore this visualization tool. There are also a number of videos on YouTube I draw from that compare algorithms sorting the same data.

Students also have to complete an assignment called Sort Race, which requires them to implement sorting algorithms and test them against data sets of varying types: reversed, already sorted, all sorted but one, and random. When they see algorithms take a significant amount of time on an already sorted list, they get why it's not the preferred solution and can then go back to the code to see what slows it down (and what doesn't slow down others in some cases).

Answer 2

For any algorithm, if you give it a large input it will fail to complete in a short time. For example, in the case of sorting algorithms, insertion sort is far less efficient than quicksort. But on a small array, insertion sort will finish almost instantaneously. On larger arrays, you'd see insertion sort get exponentially slower, and quicksort stay fairly quick. But regardless of the algorithm, eventually you can give a large enough input that it will take years to complete.

To directly answer your question, I think insertion sort is a "textbook example" of a quick to think of but inefficient algorithm. There are certainly faster algorithms, but even they, on a large enough input, will fail to complete in a reasonable time.

What is heuristics to detect such code which could be done asymptotically faster?

There really isn't a way besides practice to detect when a problem could be solved with a more efficient algorithm.

Answer 3

I think it's important that over time, students develop an understanding of how their choices as well as langauge (and library) implementation choices can affect run time. I think this basic understanding is much more important than memorizing a bunch of run times.

I take my students through some problems that lead to them "discovering" hidden complexities.

I'm linking to two blog posts I wrote about the subject:

Who won the election - quadratic to linear time

and

Hidden Complexity

Answer 4

To my knowledge, the only way to know if a more efficient solution exists is to find a correspondence to a problem with a known optimal algorithm. In general, practice & experience are necessary to develop efficiency mindfulness. One way to encourage it is to ask your students how their solutions would scale & where they expect it to fail. If you get a variety of solutions, discuss how & why they differ.

Also bear in mind that the most efficient code isn't always the best, especially for general development. Clarity, maintainability and cost (development time required) are also real world factors. Even if you're teaching an algorithm analysis course, there's more than one measure of efficiency: calculations, program size & memory requirements are often at odds with each other. Discuss the trade-offs.

Answer 5

A useful example is sorting. Quicksort becomes $O(n^2)$ in the worst case, and for big data that's even more relevant.

However, if we look at Merge Sort, its worst case is $O(n\,log_2(n))$. So for sorting large amounts of data, choosing the correct algorithm (and so implementing an algorithm in a clever way) allows the program to work with much larger data.

More examples can be found in this Cheat Helpful sheet.

Answer 6

Just like @Peter, I also begin computational complexity when I introduce sorting and searching. I touch back upon it at various times throughout the year.

(Even though the topic is not part of the AP Computer Science A curriculum, I present the concepts within that course.)

It's important to note that we don't go into great depth; my main learning target is to give them an intuitive sense of constant, logarithmic, linear, and quadratic growth.

During my first sorts/searches lecture, I have them figure out the $O$, $\Omega$, and $\Theta$ (where applicable) for every sort I present. We do, in order:

• Linear search
• Binary search

I use these two to introduce the concept of algorithmic efficiency and those three functions, and the shortcuts we can take when we figure them out $O$.

Then they practice on the following sorts:

• Bubble Sort
• Insertion Sort
• Selection Sort
• Bogosort

Later on, when we do a maze solver, I touch on algorithmic complexity again, and yet again when we look at mergesort (after we have done recursion). And yet again when we talk about adding and removing elements from the front and back of linked lists and array lists. (There is actually quite a bit of practice in this exercise)

I have found that, with one lecture and a bit of practice spread throughout the year, the students seem to pick up the concept well.