<p>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 &amp; experience are necessary to develop efficiency mindfulness. One way to encourage it is to ask your students how their solutions would scale &amp; where they expect it to fail. If you get a variety of solutions, discuss how &amp; why they differ.</p>

<p>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 &amp; memory requirements are often at odds with each other. Discuss the trade-offs.</p>

CC BY-SA 3.0
2017-06-13T19:42:43.803Z
2017-06-13T19:42:43.803Z
Pikalek
<p>A useful example is sorting. <a href="https://en.wikipedia.org/wiki/Quicksort" rel="nofollow noreferrer">Quicksort</a> becomes $O(n^2)$ in the worst case, and for big data that's even more relevant. </p>

<p>However, if we look at <a href="https://en.wikipedia.org/wiki/Merge_sort" rel="nofollow noreferrer">Merge Sort</a>, 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.</p>

<p>More examples can be found in this <a href="http://bigocheatsheet.com/" rel="nofollow noreferrer"><strike>Cheat</strike> Helpful sheet</a>.</p>

CC BY-SA 3.0
2017-06-13T19:29:38.490Z
You meant $n \log{n}$, right?
enedil
CC BY-SA 3.0
2017-06-13T19:30:10.477Z
Yes, I'll fix it. (Oops)
ItamarG3
CC BY-SA 4.0
2022-03-31T13:47:37.430Z
The quick sort worst case is really misleading. The worst case will happen in two cases: Sorted data with a stupid quick sort implementation (good implementations handle these cases in O(n)), and a DOS attack by a clever attacker knowing your exact algorithm, and for randomised Quicksort, your exact random number generator. Not practical.
gnasher729
CC BY-SA 3.0
2017-06-13T19:21:40.560Z
2017-06-14T16:52:51.607Z
2017-06-14T16:52:51.607Z
ItamarG3
<p>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.</p>
<p>(Even though the topic is not part of the AP Computer Science A curriculum, I present the concepts within that course.)</p>
<p>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.</p>
<p>During my first sorts/searches lecture, I have them figure out the <span class="math-container">$O$</span>, <span class="math-container">$\Omega$</span>, and <span class="math-container">$\Theta$</span> (where applicable) for every sort I present. We do, in order:</p>
<ul>
<li><strong>Linear search</strong></li>
<li><strong>Binary search</strong></li>
</ul>
<p>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 <span class="math-container">$O$</span>.</p>
<p>Then they practice on the following sorts:</p>
<ul>
<li><strong>Bubble Sort</strong></li>
<li><strong>Insertion Sort</strong></li>
<li><strong>Selection Sort</strong></li>
<li><strong>Bogosort</strong></li>
</ul>
<p>Later on, when we do a maze solver, I touch on algorithmic complexity again, and yet again when we look at <strong>mergesort</strong> (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)</p>
<p>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.</p>

CC BY-SA 4.0
2017-06-14T17:01:10.710Z
2022-02-08T18:22:46.220Z
2022-02-08T18:22:46.220Z
Ben I.
<p>One technique I use for sorting algorithms follows after <a href="https://video.cs50.net/2016/fall/lectures/3?t=25m58s" rel="nofollow noreferrer">CS50's demonstrations</a> of the differences among bubble sort, selection sort, and insertion sort. I have 8 students line up in the following order:</p>

<pre><code>4 - 2 - 6 - 8 - 1 - 3 - 7 - 5
</code></pre>

<p>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 <code>for</code> loops and how nested <code>for</code> loops lead to $O(n^2)$.</p>

<p>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 <a href="https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html" rel="nofollow noreferrer">visualization tool</a>. There are also a number of videos on YouTube I draw from that compare algorithms sorting the same data. </p>

<p>Students also have to complete an assignment called <a href="http://cdn.cs50.net/ap/1516/problems/3/4/3-4.html" rel="nofollow noreferrer">Sort Race</a>, 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).</p>

CC BY-SA 3.0
2017-06-14T15:22:10.150Z
2017-06-14T15:22:10.150Z
Peter
<p>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.</p>

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

<p>I'm linking to two blog posts I wrote about the subject:</p>

<p><a href="https://cestlaz.github.io/posts/2013-03-23-Who_won_the_election-Quadratic_to_Linear_Time.md" rel="nofollow noreferrer">Who won the election - quadratic to linear time</a></p>

<p>and</p>

<p><a href="https://cestlaz.github.io/posts/2014-11-17-hidden-complexity.html" rel="nofollow noreferrer">Hidden Complexity</a></p>

CC BY-SA 3.0
2017-06-13T20:00:08.810Z
The syntax highlighting markup on your first blog post doesn't seem to have rendered—you might want to take a look.
Aurora0001
CC BY-SA 3.0
2017-06-13T19:50:21.763Z
2017-06-13T19:50:21.763Z
Mike Zamansky
<p>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.</p>

<p>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.</p>

<blockquote>
  <p>What is heuristics to detect such code which could be done asymptotically faster?</p>
</blockquote>

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

CC BY-SA 3.0
2017-06-13T19:02:20.303Z
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.
enedil
CC BY-SA 3.0
2017-06-13T19:03:07.553Z
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.
thesecretmaster
CC BY-SA 3.0
2017-06-13T18:59:57.587Z
2017-06-13T18:59:57.587Z
thesecretmaster
<p>Many beginners strive to solve given problems, without thinking about efficiency of solution. </p>

<p>Consider such Python code:</p>

<pre><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)]
</code></pre>

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

<p>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?</p>

CC BY-SA 3.0
2017-06-13T18:47:27.173Z
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.
ItamarG3
CC BY-SA 3.0
2017-06-13T18:59:42.740Z
@ItamarGreen I edited
enedil
CC BY-SA 3.0
2017-06-13T19:01:44.683Z
thank you. Now it's much clearer. However I would also add what the algorithm is supposed to do.
ItamarG3
<algorithms>
How to bring attention to computational complexity?
# How to bring attention to computational complexity?

(Asked by: username_0 on 2017-06-13)

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?

**Tags:** algorithms

> **Comments:**
> **username_1**: 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.  
> **username_0**: @ItamarGreen I edited  
> **username_1**: thank you. Now it's much clearer. However I would also add what the algorithm is supposed to do.  

---

## 6 answers

### Answer by username_5 on 2017-06-14. Score: 4

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 by username_6 on 2017-06-13. Score: 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](https://cestlaz.github.io/posts/2013-03-23-Who_won_the_election-Quadratic_to_Linear_Time.md)

and

[Hidden Complexity](https://cestlaz.github.io/posts/2014-11-17-hidden-complexity.html)

> **Comments:**
> **username_7**: The syntax highlighting markup on your first blog post doesn't seem to have rendered—you might want to take a look.  

---

### Answer by username_8 on 2017-06-13. Score: 3

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.

> **Comments:**
> **username_0**: 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.  
> **username_8**: 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.  

---

### Answer by username_2 on 2017-06-13. Score: 2

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 by username_1 on 2017-06-13. Score: 2

A useful example is sorting. [Quicksort](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](http://bigocheatsheet.com/).

> **Comments:**
> **username_0**: You meant $n \log{n}$, right?  
> **username_1**: Yes, I'll fix it. (Oops)  
> **username_3**: The quick sort worst case is really misleading. The worst case will happen in two cases: Sorted data with a stupid quick sort implementation (good implementations handle these cases in O(n)), and a DOS attack by a clever attacker knowing your exact algorithm, and for randomised Quicksort, your exact random number generator. Not practical.  

---

### Answer by username_4 on 2017-06-14. Score: 1

Just like @username_5, 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.


---

