# How to bring attention to computational complexity?

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?

• Welcome to CS Educators stack exchange! This question could really use more details. Is there an example that would help us see the problem you are facing (for example, an algorithm which you would call poorly-crafted)? Please add some details to help us help you. Jun 13 '17 at 18:47
• @ItamarGreen I edited Jun 13 '17 at 18:59
• thank you. Now it's much clearer. However I would also add what the algorithm is supposed to do. Jun 13 '17 at 19:01

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

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.

• But the key is that most school code isn't run on big data, so slow solutions won't be detected. The ideal situation would be to find the problem in the phase of designing solution. Jun 13 '17 at 19:02
• As I said, I think that's just practice. Also, there isn't anything stopping you from working on "big data," is there? If you really wanted to estimate the efficiency of an algorithm, that's what big O is for. Jun 13 '17 at 19:03

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.

Who won the election - quadratic to linear time

and

Hidden Complexity

• The syntax highlighting markup on your first blog post doesn't seem to have rendered—you might want to take a look. Jun 13 '17 at 20:00

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.

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.

• You meant $n \log{n}$, right? Jun 13 '17 at 19:29
• Yes, I'll fix it. (Oops) Jun 13 '17 at 19:30

Just like @Peter, I also present computational complexity when I introduce sorting and searching. Even though the topic is not part of the AP Computer Science A curriculum, I present the concepts within that course.

During that 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$. (Along the way, they see why we so rarely examine $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).

I have found that, with one lecture and just a bit of practice, the students have little trouble understanding $O$, at least in concept. Obviously, calculating it can eventually get quite hard for some algorithms, but I don't need to take them that far.