Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T19:42:43.803Z
Answers.LastActivityDate: 2017-06-13T19:42:43.803Z
Answers.UserDisplayName: Pikalek
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T19:29:38.490Z
Answers.Text: You meant $n \log{n}$, right?
Answers.UserDisplayName: enedil
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T19:30:10.477Z
Answers.Text: Yes, I'll fix it. (Oops)
Answers.UserDisplayName: ItamarG3
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-31T13:47:37.430Z
Answers.Text: 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.
Answers.UserDisplayName: gnasher729
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T19:21:40.560Z
Answers.LastActivityDate: 2017-06-14T16:52:51.607Z
Answers.LastEditDate: 2017-06-14T16:52:51.607Z
Answers.UserDisplayName: ItamarG3
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-06-14T17:01:10.710Z
Answers.LastActivityDate: 2022-02-08T18:22:46.220Z
Answers.LastEditDate: 2022-02-08T18:22:46.220Z
Answers.UserDisplayName: Ben I.
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-14T15:22:10.150Z
Answers.LastActivityDate: 2017-06-14T15:22:10.150Z
Answers.UserDisplayName: Peter
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T20:00:08.810Z
Answers.Text: The syntax highlighting markup on your first blog post doesn't seem to have rendered—you might want to take a look.
Answers.UserDisplayName: Aurora0001
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T19:50:21.763Z
Answers.LastActivityDate: 2017-06-13T19:50:21.763Z
Answers.UserDisplayName: Mike Zamansky
Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T19:02:20.303Z
Answers.Text: 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.
Answers.UserDisplayName: enedil
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T19:03:07.553Z
Answers.Text: 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.
Answers.UserDisplayName: thesecretmaster
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-13T18:59:57.587Z
Answers.LastActivityDate: 2017-06-13T18:59:57.587Z
Answers.UserDisplayName: thesecretmaster
Body: <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>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-13T18:47:27.173Z
Comments.Text: 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.
Comments.UserDisplayName: ItamarG3
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-13T18:59:42.740Z
Comments.Text: @ItamarGreen I edited
Comments.UserDisplayName: enedil
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-06-13T19:01:44.683Z
Comments.Text: thank you. Now it's much clearer. However I would also add what the algorithm is supposed to do.
Comments.UserDisplayName: ItamarG3
Tags: <algorithms>
Title: How to bring attention to computational complexity?
ThreadText: # 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](https://video.cs50.net/2016/fall/lectures/3?t=25m58s) 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](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html). 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](http://cdn.cs50.net/ap/1516/problems/3/4/3-4.html), 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.
  
  
  ---
  
  