<p>Here are some notes I wrote when I first introduced this concept at the college level. The example came from Alex Thornton, a lecturer here at UCI. I observed him talk about this in his class, and wrote it up for my students. Extra advantage: it uses the O(1) complexity class, which sometimes throws students.</p>

<p>Suppose that you want to get from point A to point B, and you have two ways to
travel: by walking and by teleporting. If you walk, you walk at a constant
rate from A to B; if you teleport, you must wait 1 minute for the teleporter to
warm up, and then you will be instantaneously transported from A to B. Here N
(the size of the problem to solve) is the distance between A and B.</p>

<p>Now, walking is represented by the linear complexity class, O(N): if you double
the distance you need to walk, you double the time to get there. Teleportation
is represented by the constant complexity class, O(1): if you double the
distance you need to walk, the amount of time does not change to get there: it
is always 1 minute.</p>

<p>From the discussion above, because the complexity class O(1) is a lower
complexity class than O(N), we know that for a big enough distance teleportation
will be faster than walking. What is that distance? The distance we can walk in
1 minute (the amount of time it takes the teleporter to warm up). We can draw
these relationships as follows, showing where the Walk and Teleport lines cross.</p>

<pre><code>                 Walk
     time |       /
          |      /
   60 secs+-----+--------------------------- Teleport
          |    /
          |   /
          |  /
          | /
          |/
          +--------------------------------
                  PROBLEM SIZE N = DISTANCE
</code></pre>

<p>The sloping line represents the function T<sub>walk</sub>(N) = (1/speed)*N; when we remove
the constant (1/speed), this function is just O(N). The horizontal line
represent the function T<sub>teleport</sub>(N) = 60; the time is always 60 seconds. We
treat that as 60*1 (so we remove the 60 as a constant multiplier), which leaves
this function as O(1).</p>

<p>The slope of the Walk line represents the speed: slower speeds have a bigger
slope; higher speeds have a smaller slope. But no matter the slope, the Walk
line will eventually intersects the Teleport line: where both modes of
transportation take the same amount of time. For all larger distances,
teleporting will take less time than walking.</p>

<p>What if we needed 30 seconds to put on our shoes. The graphs would change
to be</p>

<pre><code>              Walk
     time |    /
          |   /
   60 secs+--+----------------------------- Teleport
          | /
          |/
   30 secs+   Putting on shoes in 30 seconds
          |
          |
          +--------------------------------
                  PROBLEM SIZE N = DISTANCE
</code></pre>

<p>The lines still cross in the same way (and still at 60 seconds, although now at
a smaller distance): the distance we can walk in 30 seconds, because that is
how much time we can walk between putting on our shoes and starting to teleport.
For these specific lines we know that walking is better (takes less time) than
teleporting for small distances, but that is because we have written out the
full equations here. Generally, when we know only that one process is O(N) and
one is O(1) we don't know which is better for small N.</p>

<p>For example, if it took us 90 seconds to put on our shoes, it would always be
faster to teleport. </p>

<pre><code>            Walk
     time | /
          |/
   90 secs+   Putting on shoes in 90 seconds
          |
          |
   60 secs+-------------------------------- Teleport
          |
          |
   30 secs|
          |
          |
          +--------------------------------
                  PROBLEM SIZE N = DISTANCE
</code></pre>

<p>Whether T<sub>walk</sub>(N) = (1/speed)*N or (1/speed)*N + 60 or T<sub>walk</sub>(N) = (1/speed) + 90,
we still say walking is O(N). So asking whether O(1) or O(N) is faster for
small sized problems is unknown: it depends on the speed and the dropped term
(either 0, 60, or 90). But regardless of constants and dropped term, we know
there is a distance, at which (and beyond) that teleporting,  O(1), is faster
than walking, O(N).</p>

CC BY-SA 3.0
2018-03-26T21:39:08.580Z
You forgot to account for the time not spent in the gim, when you walk.
ctrl-alt-delor
CC BY-SA 3.0
2018-03-26T22:15:58.983Z
If it takes time to put on shoes for walking, are you assuming that we are teleporting barefoot?
NomadMaker
CC BY-SA 3.0
2018-03-27T04:09:40.510Z
@NomadMaker: If the teleport takes longer, putting on shoes is off the critical path; you can do it while the teleport warms up and still have time to program the destination.  So the teleport time to arrive properly shod is `max(teleport_warmup,  shoes)`.
Peter Cordes
CC BY-SA 3.0
2018-03-27T04:14:16.613Z
@Richard: do you find this example leaves students confused when they *don't* have the exact function, just a complexity class?  Do they end up thinking they always need to know the constants before they can drop them, or something?  Hopefully that isn't a problem, but worth asking.  (I'm not a CS teacher other than on SO, but answering SO questions exposes me to a firehose of questions from people who failed to understand stuff I thought was obvious... as well as the rarer interesting questions about tricky stuff.)
Peter Cordes
CC BY-SA 3.0
2018-03-27T16:15:55.863Z
I wonder if it would be helpful to graph the ratio of the actual time or resource requirement to the big-O function.  While working with quotients analytically is apt to be rather troublesome, if f(x) is O(g(x)), and f(x) and g(x) are positive everywhere, then it will possible to identify an x0 and y0 such that the graph never enters the region where x>x0 and f(x)/g(x)>y0.
supercat
CC BY-SA 3.0
2018-03-26T18:15:32.320Z
2018-03-27T16:58:52.093Z
2018-03-27T16:58:52.093Z
Richard Pattis
<p>To be honest, I really hate that Big-O notation in academia seems to be universally taught in the context of sorting algorithms.  That's how I was taught, but it wasn't actually what drove home the importance of Big-O notation.</p>
<p>Instead, it was my roommate's homework assignment, which he did with the most fantastically inefficient algorithm; here's an adapted version of the problem (using C# instead of C-style linked lists)</p>
<blockquote>
<pre><code>public class LongNumberDigit
{
    public int digitValue;
    public LongNumberDigit nextDigit;
}
</code></pre>
<p>Okay, this is a simple class—it stores a single digit of a long number—as well as either a <code>NULL</code> <code>nextDigit</code>, or another <code>LongNumberDigit</code> of the next digit of the number.  So '572' would be a '5' digit, pointing to a '7' digit, pointing to a '2' digit, pointing to <code>NULL</code>.  I want you to write a function that takes two <code>LongNumberDigits</code>—each the first digit of a possibly really long number—and outputs another <code>LongNumberDigit</code> of those first two numbers multiplied together.</p>
</blockquote>
<p>This is an example of where Big-O can really shine, because your students might come up with anything from O(n<sup>2</sup>) to O(n<sup>5</sup>).  And it's very simple to:</p>
<ul>
<li>Show how you get those numbers (ultimately, everything they'll have
will be simple loops.)</li>
<li>Show how drastically that Big-O notation can impact things with large
values</li>
<li>Show how changing an algorithm just a little bit can have huge impacts on
the Big-O notation.</li>
</ul>
<p>Whereas, with sorting, it's more mathematically challenging and abstract to get a Big-O value, and it's not as satisfying—basically, O(n*n) versus O(n*log(n))</p>
<p>Not saying you have to use this exact example.  Just find something that requires them to write an algorithm that:</p>
<ol>
<li>Generally will involve simple loops</li>
<li>Can have a wildly different levels of efficiency depending on how
they design it.</li>
</ol>

CC BY-SA 3.0
2018-03-26T22:35:37.127Z
What in the world did your roommate do that was so inefficient?  I am having trouble imagining.
Ben I.
CC BY-SA 3.0
2018-03-27T04:19:02.770Z
@BenI. It's a singly-linked list *going from MSB to LSB*.  Carry propagates in the other direction!!  Presumably there were getter / setter functions that took an integer digit position, and traversed the list each time for each access to each digit, in an extended-precision multiply!  So element access is O(n), and a slow O(n) at that.
Peter Cordes
CC BY-SA 3.0
2018-03-27T04:27:36.293Z
If indexing is from the LSB, it might walk the list once to get length, then walk it again to reach the right element.  That's only increasing the constant factor, so the whole linked-list storage scheme only raises the complexity class by a factor of `n`, but what a huge constant factor.  Pointer chasing has latency that out-of-order execution can't hide easily, vs. array indexing with non-data-dependent offsets.
Peter Cordes
CC BY-SA 3.0
2018-03-27T13:21:26.883Z
FWIW, here's the alg my roommate came up with: Loop a counter from 1 to the length of the first number (n). For each value, start at the beginning and iterate to the correct spot in the linked list (n*n).  Do a second interior loop for the second number (n^3) and then iterate to the correct spot in the linked list (n^4).  Finally, iterate to the correct spot to put the information in the answer's linked list (n^5).  The reason it was so inefficient is because he didn't walk to the next node in those linked lists - he started over at the beginning each time.  Which Big-O helps analyze awesomely
Kevin
CC BY-SA 3.0
2018-03-26T18:15:05.473Z
2018-03-27T13:50:10.613Z
2020-06-18T08:36:57.023Z
Kevin
<p>One good overall educational strategy is to teach the same thing to students repeatedly, using a Spiral approach, in which each turn of the spiral teaches at a deeper level. Don't expect the students to completely get much of anything at the first mention of it, but reinforce the ideas and deepen the knowledge. You can do this for many things in one course, but you can also do it over a student's career. </p>

<p>As you say, it is a mathematical concept and students may not yet have the tools needed to completely get it, but you can start, and you can give them enough insight so that when <code>Big O</code> comes up later, say in their undergraduate education, they have some prior basis for understanding it more deeply.  </p>

<p>However, it is important that you don't oversimplify the topic or to give them false information, leading them to misconceptions that require <em>un-learning</em> later. So, first, be honest: the topic is mathematical, it is a bit deep, we can only scratch the surface a bit. </p>

<p>For young students without a solid algebra background and little exposure to calculus, it might be good to start with a <a href="https://www.desmos.com/calculator" rel="noreferrer">graphing calculator</a> so that students can see what happens to common functions as the independent variable increases. Graphing $log(x)$, $x$, $x^2$, $2^x$ etc is a start. Graphing $1000x + x^2$ can give them the idea that the high order term dominates the growth. If they can <em>see</em> it, you don't need to depend on their knowledge from elsewhere. </p>

<p>Next, you can show them a few algorithms and look at the actual run times, noting that you are only giving them an idea. One of my favorite "tricks" is to ask students who have seen a few sort algorithms, to come up with the most inefficient sort algorithm they can think of. With a good randomizer even repeatedly randomizing an array and then checking to see if it is sorted <em>is</em> an algorithm by the law of large numbers. If they know about permutations they can even calculate the maximum number of iterations needed to sort. If they are not likely to know that from other places, then computing permutations can be an earlier programming exercise. </p>

<p>The problem with teaching the first cycle of a deep knowledge of Big O is that it is easy to give the wrong impression about a lot of things depending on the words and examples you use. If you say that, for example, bubble sort is $O(n^2)$ you are correct, but it may have little meaning. It doesn't mean, however that the "running time" of bubble sort is $n^2$, but (if $n^2$ is the best bound) that it is "proportional to $n^2$ for large values of n." It is easy to forget to say those extra words: "proportional", "large...". It is also easy to forget that Big O is about upper bounds, only. So technically, Bubble Sort is also $O(2^n)$, but it would probably not be wise to stress that in the first cycle of learning outside a mathematics class. </p>

<p>Also, the examples matter. Bubble sort (if unoptimized) always runs in quadratic time and you can see that from the algorithm. It depends only on the size of the data set. But insertion sort is different. The normal program has two nested loops, just like bubble sort, but if the original dataset is already nearly sorted (by some measure of "nearly") then it actually runs in near linear time - or even linear time, for some examples. But it is still a quadratic algorithm, since its <em>worst case</em> behavior is quadratic. So, "worst case" is another important word to keep emphasizing. </p>

<p>You also need to mention, but probably not stress, is that efficiency need not be determined by the size of the data set necessarily. Factoring large numbers is an example. There is only one number to factor, but it is harder to do for larger numbers since (for brute force, anyway), the difficulty is determined by the number of possible solutions, which is itself large (but can be estimated). </p>

<p>A third complication is that it isn't always <em>time</em> complexity that is needed. <em>Space</em> complexity is also often important. How much "scratch" space does an algorithm need for datasets of different sizes (or datasets of different complexity, or ...). A <a href="https://arxiv.org/pdf/1803.03453v1.pdf" rel="noreferrer">recent (early 2018) experiment</a>(pdf) in Artificial Intelligence, pitted two different AIs against one another. One of them "learned" that it could "win" the competition by forcing the other to use more and more memory space, resulting in a crash of the other. </p>

<p>Another idea to get across is that if the numbers (data set size for example) are small, then using a highly efficient algorithm may be worse than one theoretically more "inefficient". <code>Big O</code> is about asymptotic behavior, of course and the more efficient algorithm may be more complex and actually be worse on small data sets as well as being, perhaps, more likely to be buggy. Some quick sorters, for example, revert to a quadratic algorithm once the split gets the datasets small enough. I once built a product that had an exponential algorithm embedded in it. That worked, since the likelihood of a large dataset was vanishingly small. Integer Programming is actually done by real programs in the real world in spite of the complexity of the problem itself. </p>

<p>Finally you need to note that <code>Big O</code> is about algorithms. That is related to the <em>complexity</em> of problems, but isn't exactly the same thing. There are a lot of array sorting algorithms and they have different exponential behavior. But the problem itself has an inherent complexity. For sorting <code>int</code> or <code>long</code> values (the built in data types) in a computer, the complexity is actually linear (Radix Sort). You need some sort of a BigNum data type before you reach $O(n*log(n))$, since the number of possible values in int is bounded. And for large numbers of arbitrarily large values, you start to run into space problems for most purposes. </p>

<p>Let me note, for completeness, prompted by a "conversation" in comments here with user RiaD, that any algorithm that is $O(n^2)$, such as Bubble Sort, is also $O(n^3)$ and $O(n^4)$ and $O(2^n)$, since all of those other functions dominate $g(n) = n^2$. One normally gives a "good" estimate, but the "worse" estimates for growth apply by default. </p>

<p>tl;dr: Say what's true. It is a complex, mathematical topic. Examples are good. Deep understanding can come later. Completeness isn't essential in the first cycle of understanding. Take that into account when testing. </p>

CC BY-SA 3.0
2018-03-27T21:19:45.370Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/75164/discussion-on-answer-by-buffy-how-do-you-teach-big-o-to-high-schoolers-with-vary).
Peter
CC BY-SA 3.0
2018-03-27T22:41:31.940Z
Related: [Bubble Sort: An Archaeological Algorithmic Analysis](https://users.cs.duke.edu/~ola/papers/bubble.pdf) is an interesting read about the origins of the algo, and it's popularity as a teaching example.
Peter Cordes
CC BY-SA 3.0
2018-03-26T13:12:52.587Z
2018-03-27T16:01:50.133Z
2018-03-27T16:01:50.133Z
Buffy
<p>I learned to program a long time before I'd ever <em>heard</em> of "Big O Notation" or any other formal analysis of algorithms, asymptotic or otherwise. Three plus decades into my programming, I read a book  by <a href="https://www.cs.vt.edu/user/48" rel="noreferrer" title="Professor Clifford A. Shaffer">Clifford A. Shaffer</a> of <a href="https://vt.edu/" rel="noreferrer">Virginia Tech</a>, <em><a href="https://rads.stackoverflow.com/amzn/click/B007EID7AQ" rel="noreferrer">A Practical Introduction to Data Structures and Algorithm Analysis</a></em>. It has since been republished as <em>Data Structures and Algorithm Analysis</em> with version in <a href="https://rads.stackoverflow.com/amzn/click/048648582X" rel="noreferrer">C++</a> and <a href="https://rads.stackoverflow.com/amzn/click/0486485811" rel="noreferrer">Java</a>.
Both the <a href="https://drive.google.com/open?id=1b18p0Zd4jbRxXQ1tebTmzLsdEDBcEEkH" rel="noreferrer">C++ version</a> and <a href="https://drive.google.com/open?id=1zjF5kdOd9iKxzaHIT_FXo4HZw4s7-1EO" rel="noreferrer">Java version</a> are available <a href="https://people.cs.vt.edu/shaffer/Book/" rel="noreferrer">online</a> along with lots all of the <a href="https://people.cs.vt.edu/shaffer/Book/JAVA/CS3114_09212011.ppt" rel="noreferrer" title="Download the PowerPoint presentation">resources</a>, <a href="https://people.cs.vt.edu/shaffer/Book/Assignments.html" rel="noreferrer" title="A collection of programming assignments that the author has used">assignments</a>, and <a href="https://people.cs.vt.edu/shaffer/Book/C++3e/progs" rel="noreferrer">C++</a> and <a href="https://people.cs.vt.edu/shaffer/Book/JAVA/progs" rel="noreferrer">Java</a> source codes for using the books in class.</p>

<blockquote>
  <p><a href="https://books.google.com/books/about/A_Practical_Introduction_to_Data_Structu.html?id=uPwkAQAAIAAJ" rel="noreferrer"><img src="https://i.sstatic.net/4xqiYt.jpg" alt="A Practical Introduction to Data Structures and Algorithm Analysis, 2nd edition" title="A Practical Introduction to Data Structures and Algorithm Analysis Second Edition"></a>&nbsp;&nbsp;&nbsp;&nbsp;
  <a href="http://store.doverpublications.com/048648582x.html" rel="noreferrer"><img src="https://i.sstatic.net/axbBat.jpg" alt="Data Structures and Algorithm Analysis in C++" title="Data Structures and Algorithm Analysis in C++ Third Edition"></a>&nbsp;&nbsp;&nbsp;&nbsp;
  <a href="http://store.doverpublications.com/0486485811.html" rel="noreferrer"><img src="https://i.sstatic.net/gazdrt.jpg" alt="Data Structures and Algorithm Analysis in Java" title="Data Structures and Algorithm Analysis in Java Third Edition"></a></p>
</blockquote>

<p>When I first read chapter 3, <em>Algorithm Analysis</em>, I basically said to myself, "Yeah, I got that." After all, I'd been programming for a while, and I had a good <em>sense</em> about how complex an algorithm was, and didn't need any formal notation, or explanation for it. Later, after it had percolated through my brain for a while, I realized that it <em>was</em> rather handy to have a way to explain to others, including customers and managers, why doing it <em>this</em> way would take more time, even if it saved disk space, or, on the other hand, why <em>that</em> way was doing the job fast, but the disk access was the bottleneck in program speed. All I could remember from the first breeze through the chapter was that it had a lot of mathematics involved, including things like $O(n log n)$, $T(n)=O(f(n))$, and such. I knew I'd seen at least one $\sum_{i=0}^n = yada + yada$ type expression in there somewhere as well.</p>

<p>Never having studied Calculus I was rather intimidated by the thought of all that math. (I like math pretty well, and I also know what I don't know.) Still, I had the book and I had the time, so it couldn't hurt to go back and <em>study</em> that chapter again. On the second reading I realized that while there was math <em>involved</em>, there wasn't really any math <em>performed</em>. Rather the concepts of math were used to <em>explain</em> what was being analyzed and how that affected teh growth rate. The concepts were important, but never once did an equation need to be <em>solved</em>. Furthermore, just in case the student did not understand the relationships between $10n$, $n log n$, $n^2$, $2^n$, and $n!$ the author included graphs and tables.</p>

<blockquote>
  <p><a href="https://i.sstatic.net/cqLCv.png" rel="noreferrer"><img src="https://i.sstatic.net/cqLCvl.png" alt="Sample graph"></a></p>
  
  <p><a href="https://i.sstatic.net/Bg1KP.png" rel="noreferrer"><img src="https://i.sstatic.net/Bg1KPl.png" alt="Sample table"></a></p>
</blockquote>

<p>The language of the books is aimed at college-level students, and the equations and explanations seem to assume the student has a prior understanding of the "language" used in the mathematical analysis. Therefore, I couldn't recommend using that as the textbook for the class, or even for that segment of class. I can, however, recommend it as an excellent starting point for <em>your</em> lesson plan. Using the progression of his explanations for <em>finding</em> the growth rate of an algorithm, you can rework the examples, and the application of mathematical <em>concepts</em> so that it better fits the knowledge of your students, and carry it forward in a manner consistent with your style in the class so far. The method used to show, and find, growth rates, and the Big $\Bbb O$, Big $\Omega$, and Big $\Theta$ are decidedly <em>non-math</em> in their application, and adjusting the material for the students you see in your classroom should be reasonably simple.</p>

<p>I agree that you should give your students the exposure to the subject, and deepen that exposure as much as the curriculum will allow. I've found, after learning from that chapter, that I am equipped to explain my analysis of a routine, and its possible optimizations, much better to other programmers - whether they know Big $\Bbb O$ notation or not. If someone <em>does</em> know Big $\Bbb O$, it is an excellent shortcut to explaining why a routine is slow, and if they <em>do not</em> know Big $\Bbb O$, I am now able to quantify and explain what I used to intuit and couldn't explain.</p>

<h3>The <em>Mathematics</em> Involved</h3>

<p>Again, the mathematics is more for explaining the results than for finding them. Understanding what the graph looks like helps a lot, by orders of magnitude. The online <a href="https://www.desmos.com/calculator" rel="noreferrer">graphing calculator</a> mentioned by <a href="https://cseducators.stackexchange.com/users/1293/buffy">Buffy</a> in another <a href="https://cseducators.stackexchange.com/a/4555/104">answer</a> is an excellent way to deal with the math involved in understanding the <em>growth rate</em> that Big $\Bbb O$ notation signifies. I once made a similar, if <em>much</em> simpler, tool for explaining the concepts of linear, logarithmic, and quadratic to GED students. What they couldn't grasp with words and text, the readily apprehended with interactive visuals.</p>

<h3>The Testing</h3>

<p>As this will be the introduction to Big $\Bbb O$ notation, and at that only a "dip your toe in the water" type exposure, testing on the subject probably shouldn't be very intense. If you covered the complexity of heap sort and can write a heap sort in a manner they have not seen, then use that and ask them to find the Big $\Bbb O$ of the new version. It's still a heap sort, and they should be able to reach the same results as for the one they've already seen. Additionally, with some short code fragments, have them classify the fragments, or use pairs or fragments, and ask for the one with the better Big $\Bbb O$ for a significantly large value of $n$. The idea is to reinforce the usefulness of the analysis, and that Big $\Bbb O$ notation is only a simple, common, way of expressing the complexity that allows for comparing algorithms and selecting which one to use in a new situation. Leave the finer details for later courses when, and if, they pursue a CS curriculum.</p>

CC BY-SA 3.0
2018-03-27T13:00:55.127Z
While drawing asymptotic behaviour is fine, you should be careful to include that making an asymptotic claim from a drawing is a dangerous exercise that shouldn't be attempted unless the student knows what that means!
Discrete lizard
CC BY-SA 3.0
2018-03-28T12:02:48.570Z
In the table of results, I would add a sample how the time grow for each complexity. For instance base the fact that at n=100 O(n) take 1s and show us the time that it represent, people will understand that much better.
Walfrat
CC BY-SA 3.0
2018-03-27T11:03:27.060Z
2018-03-27T11:03:27.060Z
Gypsy Spellweaver
<p>What I always do is to look at multiplying by $2$, as everyone can multiply by $2$.</p>

<p>Consider $O(n)$ (linear) time, if you double $n$, then the running time doubles* (okay, not precisely, I'm assuming $c\cdot n$ here. But this is a preparation, let's just assume we have only the leading term. If you think this is important, add this) </p>

<p>Now look at $O(n^2)$ (quadratic), here doubling $n$ gives us a running time of $4$ times the original! Wow! This isn't fun!</p>

<p>Now, bonus, consider $O(2^n)$ and lets multiply by $2$ again! Uh oh. The answer now is $2^n$ times longer than before. This is bad! Let's stick to polynomial running times!</p>

<p>Oh and this works with $O(1)$ as well. What happens if I double $n$? Nothing! It remains $O(1)$!</p>

CC BY-SA 3.0
2018-03-27T16:59:45.973Z
Funny you should mention this.  A student came to me yesterday during lunch and did the very same analysis on the board to make sure she understood the concept.
Java Jive
CC BY-SA 3.0
2018-03-27T17:10:10.567Z
@JavaJive This is so simple that everyone can think of it. That alone already makes it useful for teaching, IMO.
Discrete lizard
CC BY-SA 3.0
2018-03-26T18:19:14.560Z
2018-03-27T04:49:44.663Z
2018-03-27T04:49:44.663Z
Discrete lizard
<p>Teach it as a pure concept and not as a mathematical formula. Big O simply describes how your algorithms runtime behaves as your data increases. </p>

<p>Let's say you are looking for a certain item out of a pile of 10 items. Let's look at an algorithm which is essentially "pick up each item and check it, and set it aside if it isn't the one and keep picking". That algorithm may be fine and perform within a runtime that meets expectations, but as the number of items in the pile increases, the runtime does too. If the number of items increases to billions, the runtime may become unacceptable. </p>

<p>In this example, the Big O is basically linear. As the number of items increases the runtime increases in a linear fashion. It is important to understand the Big O of your algorithm from the start because that can help you avoid starting out with a bad algorithm. </p>

<p>To illustrate that, now consider that we started with an algorithm that just inspects one item, checks to see if it is the one and if not throw it back into the pile, then repeat. In other words, we don't set the ones we know aren't the item aside. Now our algorithm is very inefficient and has an exponential Big O because there is potential to inspect items more than once. It could also happen that the algorithm never finishes at all, and the likelihood of that happening increases as the number of items gets humongous.  </p>

<p>If we happened to start with that idea, and pause to understand the Big O, we'd have started with the better algorithm. Searches of unmanaged data should be linear, meaning the worst scenario in searching n items is that you have to pick and examine all n items. </p>

<p>Now you move into ways we get better than linear performance. If you have control over how the pool of items you will search is organized, and you can insert them in a sorted fashion, then your search can be better than linear. </p>

<p>Or, if you take the time to index the items, your algorithm can be much better than linear. A good example is a library -- books are arranged by section, then by author. You don't have to search every book in the library to find the one you seek. The library also has a card catalog, so you don't have to search at all. </p>

<p>But there is work/time involved in organizing and maintaining the library and its catalog. But it makes sense to accept this overhead because the volume of books that come in is much, much lower than the volume of searches. It also takes space. An organized library has a larger physical footprint than it would have if the books were not organized for better searching. The card catalog takes space too. </p>

<p>A computer scientist weighs all the constraints and device the best strategy. Any algorithm for searching that is better than linear will slow down the additions and changes of items into the pool. If the items are added/removed/changed a lot more frequently than they are searched, then an index search may not be a good choice. </p>

<p>I would expect high school students that understand these concepts to be able to answer questions on a test that propose a search algorithm, and provide the key constraints, and ask "is this a good strategy?" or "how might this strategy be improved and what down-sides should be considered?" </p>

<p>When you can ignore the overhead that inserting/updating the data in an organized (or even indexed) fashion then it makes sense to target a better than linear approach. But when you can't ignore that because the volume of add/delete/updates is huge, and cannot be slowed down, then it makes sense to target a linear approach. </p>

<p>I'd expect junior computer science students to be able to understand the considerations and make choices and explain their choice. If they can do that but cannot necessarily express it in formal mathematical language, I'd be OK with that. But as an educator you would need to align to whatever your district/state expects, because if ultimately then end up taking a standardized test that does not focus on concepts and does focus on mathematical formulas, that would not work. </p>

<p>If your school aligns to the below, then what I describe above would work: </p>

<p><a href="https://k12cs.org/framework-statements-by-concept/#jump-algorithms-programming" rel="nofollow noreferrer">https://k12cs.org/framework-statements-by-concept/#jump-algorithms-programming</a></p>

<p>Because as 12th grade student:</p>

<p>"Analysis using sophisticated mathematical notation to classify algorithm performance, such as Big-O notation, is not expected."</p>

CC BY-SA 3.0
2018-03-27T13:01:47.350Z
2018-03-27T13:01:47.350Z
Thomas Carlisle
<p>My second semester programming curriculum includes a searching and sorting unit and mentions Big O notation, giving the notation for each search and sort we implement.  It does not show the derivations but does show how you can deduce some Big Os by looking at the structure of the code.</p>

<p>The course that I am teaching is called <em>Programming II</em>.  Programming II is the basic concepts of programming I (variables, decisions, loops, arrays, functions) again in a different language (C# as opposed to VB.NET), plus object-oriented principles, multi-D arrays, file I/O, searching and sorting, collections, interfaces, and some other minor language features of C#.</p>

<p>My district allows very limited prerequisite specification, meaning the only prerequisite for Programming II is Programming I.  (Programming I has no prerequisites.)  This means I have a widely varying level of mathematics exposure/competency for the students who come into the second semester course.  I struggle with how much or how little to say or share about Big O notation.  I want my students to have exposure because I know they will see it later in their CS careers, but I don't want to scare them away with "math".  And I have to account for their differing math skills.</p>

<p>Have you taught Big O to high schoolers?  What methods did you use?  How do you deal with their differing levels of math?  Is it a good idea to teach them derivations?  On tests, do you require them to do derivations or have them parrot back Big Os for various algorithms?</p>

CC BY-SA 3.0
2018-03-27T08:52:58.253Z
Just a heads-up. Be prepared for ridiculous amounts of giggling at the phrase "Big O".
AJFaraday
CC BY-SA 3.0
2018-03-27T16:57:19.403Z
To my great relief, @AJFaraday, there was no giggling when I used the term in the classroom.  Maybe they are still too naive.  Small gifts.
Java Jive
<curriculum-design><lesson-ideas><secondary-education>
How do you teach Big O to high schoolers with varying degrees of math exposure?
# How do you teach Big O to high schoolers with varying degrees of math exposure?

(Asked by: username_0 on 2018-03-26)

My second semester programming curriculum includes a searching and sorting unit and mentions Big O notation, giving the notation for each search and sort we implement. It does not show the derivations but does show how you can deduce some Big Os by looking at the structure of the code.

The course that I am teaching is called *Programming II*. Programming II is the basic concepts of programming I (variables, decisions, loops, arrays, functions) again in a different language (C# as opposed to VB.NET), plus object-oriented principles, multi-D arrays, file I/O, searching and sorting, collections, interfaces, and some other minor language features of C#.

My district allows very limited prerequisite specification, meaning the only prerequisite for Programming II is Programming I. (Programming I has no prerequisites.) This means I have a widely varying level of mathematics exposure/competency for the students who come into the second semester course. I struggle with how much or how little to say or share about Big O notation. I want my students to have exposure because I know they will see it later in their CS careers, but I don't want to scare them away with "math". And I have to account for their differing math skills.

Have you taught Big O to high schoolers? What methods did you use? How do you deal with their differing levels of math? Is it a good idea to teach them derivations? On tests, do you require them to do derivations or have them parrot back Big Os for various algorithms?

**Tags:** curriculum-design, lesson-ideas, secondary-education

> **Comments:**
> **username_1**: Just a heads-up. Be prepared for ridiculous amounts of giggling at the phrase "Big O".  
> **username_0**: To my great relief, @username_1, there was no giggling when I used the term in the classroom.  Maybe they are still too naive.  Small gifts.  

---

## 6 answers

### Answer by username_9 on 2018-03-26. Score: 24

One good overall educational strategy is to teach the same thing to students repeatedly, using a Spiral approach, in which each turn of the spiral teaches at a deeper level. Don't expect the students to completely get much of anything at the first mention of it, but reinforce the ideas and deepen the knowledge. You can do this for many things in one course, but you can also do it over a student's career.

As you say, it is a mathematical concept and students may not yet have the tools needed to completely get it, but you can start, and you can give them enough insight so that when `Big O` comes up later, say in their undergraduate education, they have some prior basis for understanding it more deeply.

However, it is important that you don't oversimplify the topic or to give them false information, leading them to misconceptions that require *un-learning* later. So, first, be honest: the topic is mathematical, it is a bit deep, we can only scratch the surface a bit.

For young students without a solid algebra background and little exposure to calculus, it might be good to start with a [graphing calculator](https://www.desmos.com/calculator) so that students can see what happens to common functions as the independent variable increases. Graphing $log(x)$, $x$, $x^2$, $2^x$ etc is a start. Graphing $1000x + x^2$ can give them the idea that the high order term dominates the growth. If they can *see* it, you don't need to depend on their knowledge from elsewhere.

Next, you can show them a few algorithms and look at the actual run times, noting that you are only giving them an idea. One of my favorite "tricks" is to ask students who have seen a few sort algorithms, to come up with the most inefficient sort algorithm they can think of. With a good randomizer even repeatedly randomizing an array and then checking to see if it is sorted *is* an algorithm by the law of large numbers. If they know about permutations they can even calculate the maximum number of iterations needed to sort. If they are not likely to know that from other places, then computing permutations can be an earlier programming exercise.

The problem with teaching the first cycle of a deep knowledge of Big O is that it is easy to give the wrong impression about a lot of things depending on the words and examples you use. If you say that, for example, bubble sort is $O(n^2)$ you are correct, but it may have little meaning. It doesn't mean, however that the "running time" of bubble sort is $n^2$, but (if $n^2$ is the best bound) that it is "proportional to $n^2$ for large values of n." It is easy to forget to say those extra words: "proportional", "large...". It is also easy to forget that Big O is about upper bounds, only. So technically, Bubble Sort is also $O(2^n)$, but it would probably not be wise to stress that in the first cycle of learning outside a mathematics class.

Also, the examples matter. Bubble sort (if unoptimized) always runs in quadratic time and you can see that from the algorithm. It depends only on the size of the data set. But insertion sort is different. The normal program has two nested loops, just like bubble sort, but if the original dataset is already nearly sorted (by some measure of "nearly") then it actually runs in near linear time - or even linear time, for some examples. But it is still a quadratic algorithm, since its *worst case* behavior is quadratic. So, "worst case" is another important word to keep emphasizing.

You also need to mention, but probably not stress, is that efficiency need not be determined by the size of the data set necessarily. Factoring large numbers is an example. There is only one number to factor, but it is harder to do for larger numbers since (for brute force, anyway), the difficulty is determined by the number of possible solutions, which is itself large (but can be estimated).

A third complication is that it isn't always *time* complexity that is needed. *Space* complexity is also often important. How much "scratch" space does an algorithm need for datasets of different sizes (or datasets of different complexity, or ...). A [recent (early 2018) experiment](https://arxiv.org/pdf/1803.03453v1.pdf)(pdf) in Artificial Intelligence, pitted two different AIs against one another. One of them "learned" that it could "win" the competition by forcing the other to use more and more memory space, resulting in a crash of the other.

Another idea to get across is that if the numbers (data set size for example) are small, then using a highly efficient algorithm may be worse than one theoretically more "inefficient". `Big O` is about asymptotic behavior, of course and the more efficient algorithm may be more complex and actually be worse on small data sets as well as being, perhaps, more likely to be buggy. Some quick sorters, for example, revert to a quadratic algorithm once the split gets the datasets small enough. I once built a product that had an exponential algorithm embedded in it. That worked, since the likelihood of a large dataset was vanishingly small. Integer Programming is actually done by real programs in the real world in spite of the complexity of the problem itself.

Finally you need to note that `Big O` is about algorithms. That is related to the *complexity* of problems, but isn't exactly the same thing. There are a lot of array sorting algorithms and they have different exponential behavior. But the problem itself has an inherent complexity. For sorting `int` or `long` values (the built in data types) in a computer, the complexity is actually linear (Radix Sort). You need some sort of a BigNum data type before you reach $O(n\*log(n))$, since the number of possible values in int is bounded. And for large numbers of arbitrarily large values, you start to run into space problems for most purposes.

Let me note, for completeness, prompted by a "conversation" in comments here with user RiaD, that any algorithm that is $O(n^2)$, such as Bubble Sort, is also $O(n^3)$ and $O(n^4)$ and $O(2^n)$, since all of those other functions dominate $g(n) = n^2$. One normally gives a "good" estimate, but the "worse" estimates for growth apply by default.

tl;dr: Say what's true. It is a complex, mathematical topic. Examples are good. Deep understanding can come later. Completeness isn't essential in the first cycle of understanding. Take that into account when testing.

> **Comments:**
> **username_10**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/75164/discussion-on-answer-by-buffy-how-do-you-teach-big-o-to-high-schoolers-with-vary).  
> **username_5**: Related: [Bubble Sort: An Archaeological Algorithmic Analysis](https://users.cs.duke.edu/~ola/papers/bubble.pdf) is an interesting read about the origins of the algo, and it's popularity as a teaching example.  

---

### Answer by username_2 on 2018-03-26. Score: 11

Here are some notes I wrote when I first introduced this concept at the college level. The example came from Alex Thornton, a lecturer here at UCI. I observed him talk about this in his class, and wrote it up for my students. Extra advantage: it uses the O(1) complexity class, which sometimes throws students.
Suppose that you want to get from point A to point B, and you have two ways to
travel: by walking and by teleporting. If you walk, you walk at a constant
rate from A to B; if you teleport, you must wait 1 minute for the teleporter to
warm up, and then you will be instantaneously transported from A to B. Here N
(the size of the problem to solve) is the distance between A and B.
Now, walking is represented by the linear complexity class, O(N): if you double
the distance you need to walk, you double the time to get there. Teleportation
is represented by the constant complexity class, O(1): if you double the
distance you need to walk, the amount of time does not change to get there: it
is always 1 minute.
From the discussion above, because the complexity class O(1) is a lower
complexity class than O(N), we know that for a big enough distance teleportation
will be faster than walking. What is that distance? The distance we can walk in
1 minute (the amount of time it takes the teleporter to warm up). We can draw
these relationships as follows, showing where the Walk and Teleport lines cross.
                 Walk
     time |       /
          |      /
   60 secs+-----+--------------------------- Teleport
          |    /
          |   /
          |  /
          | /
          |/
          +--------------------------------
                  PROBLEM SIZE N = DISTANCE

The sloping line represents the function Twalk(N) = (1/speed)*N; when we remove
the constant (1/speed), this function is just O(N). The horizontal line
represent the function Tteleport(N) = 60; the time is always 60 seconds. We
treat that as 60*1 (so we remove the 60 as a constant multiplier), which leaves
this function as O(1).
The slope of the Walk line represents the speed: slower speeds have a bigger
slope; higher speeds have a smaller slope. But no matter the slope, the Walk
line will eventually intersects the Teleport line: where both modes of
transportation take the same amount of time. For all larger distances,
teleporting will take less time than walking.
What if we needed 30 seconds to put on our shoes. The graphs would change
to be
              Walk
     time |    /
          |   /
   60 secs+--+----------------------------- Teleport
          | /
          |/
   30 secs+   Putting on shoes in 30 seconds
          |
          |
          +--------------------------------
                  PROBLEM SIZE N = DISTANCE

The lines still cross in the same way (and still at 60 seconds, although now at
a smaller distance): the distance we can walk in 30 seconds, because that is
how much time we can walk between putting on our shoes and starting to teleport.
For these specific lines we know that walking is better (takes less time) than
teleporting for small distances, but that is because we have written out the
full equations here. Generally, when we know only that one process is O(N) and
one is O(1) we don't know which is better for small N.
For example, if it took us 90 seconds to put on our shoes, it would always be
faster to teleport. 
            Walk
     time | /
          |/
   90 secs+   Putting on shoes in 90 seconds
          |
          |
   60 secs+-------------------------------- Teleport
          |
          |
   30 secs|
          |
          |
          +--------------------------------
                  PROBLEM SIZE N = DISTANCE

Whether Twalk(N) = (1/speed)*N or (1/speed)*N + 60 or Twalk(N) = (1/speed) + 90,
we still say walking is O(N). So asking whether O(1) or O(N) is faster for
small sized problems is unknown: it depends on the speed and the dropped term
(either 0, 60, or 90). But regardless of constants and dropped term, we know
there is a distance, at which (and beyond) that teleporting,  O(1), is faster
than walking, O(N).

> **Comments:**
> **username_3**: You forgot to account for the time not spent in the gim, when you walk.  
> **username_4**: If it takes time to put on shoes for walking, are you assuming that we are teleporting barefoot?  
> **username_5**: @username_4: If the teleport takes longer, putting on shoes is off the critical path; you can do it while the teleport warms up and still have time to program the destination.  So the teleport time to arrive properly shod is `max(teleport_warmup,  shoes)`.  
> **username_5**: @Richard: do you find this example leaves students confused when they *don't* have the exact function, just a complexity class?  Do they end up thinking they always need to know the constants before they can drop them, or something?  Hopefully that isn't a problem, but worth asking.  (I'm not a CS teacher other than on SO, but answering SO questions exposes me to a firehose of questions from people who failed to understand stuff I thought was obvious... as well as the rarer interesting questions about tricky stuff.)  
> **username_6**: I wonder if it would be helpful to graph the ratio of the actual time or resource requirement to the big-O function.  While working with quotients analytically is apt to be rather troublesome, if f(x) is O(g(x)), and f(x) and g(x) are positive everywhere, then it will possible to identify an x0 and y0 such that the graph never enters the region where x>x0 and f(x)/g(x)>y0.  

---

### Answer by username_7 on 2018-03-26. Score: 9

To be honest, I really hate that Big-O notation in academia seems to be universally taught in the context of sorting algorithms.  That's how I was taught, but it wasn't actually what drove home the importance of Big-O notation.
Instead, it was my roommate's homework assignment, which he did with the most fantastically inefficient algorithm; here's an adapted version of the problem (using C# instead of C-style linked lists)

public class LongNumberDigit
{
    public int digitValue;
    public LongNumberDigit nextDigit;
}

Okay, this is a simple class—it stores a single digit of a long number—as well as either a NULL nextDigit, or another LongNumberDigit of the next digit of the number.  So '572' would be a '5' digit, pointing to a '7' digit, pointing to a '2' digit, pointing to NULL.  I want you to write a function that takes two LongNumberDigits—each the first digit of a possibly really long number—and outputs another LongNumberDigit of those first two numbers multiplied together.

This is an example of where Big-O can really shine, because your students might come up with anything from O(n2) to O(n5).  And it's very simple to:

Show how you get those numbers (ultimately, everything they'll have
will be simple loops.)
Show how drastically that Big-O notation can impact things with large
values
Show how changing an algorithm just a little bit can have huge impacts on
the Big-O notation.

Whereas, with sorting, it's more mathematically challenging and abstract to get a Big-O value, and it's not as satisfying—basically, O(n*n) versus O(n*log(n))
Not saying you have to use this exact example.  Just find something that requires them to write an algorithm that:

Generally will involve simple loops
Can have a wildly different levels of efficiency depending on how
they design it.

> **Comments:**
> **username_8**: What in the world did your roommate do that was so inefficient?  I am having trouble imagining.  
> **username_5**: @BenI. It's a singly-linked list *going from MSB to LSB*.  Carry propagates in the other direction!!  Presumably there were getter / setter functions that took an integer digit position, and traversed the list each time for each access to each digit, in an extended-precision multiply!  So element access is O(n), and a slow O(n) at that.  
> **username_5**: If indexing is from the LSB, it might walk the list once to get length, then walk it again to reach the right element.  That's only increasing the constant factor, so the whole linked-list storage scheme only raises the complexity class by a factor of `n`, but what a huge constant factor.  Pointer chasing has latency that out-of-order execution can't hide easily, vs. array indexing with non-data-dependent offsets.  
> **username_7**: FWIW, here's the alg my roommate came up with: Loop a counter from 1 to the length of the first number (n). For each value, start at the beginning and iterate to the correct spot in the linked list (n*n).  Do a second interior loop for the second number (n^3) and then iterate to the correct spot in the linked list (n^4).  Finally, iterate to the correct spot to put the information in the answer's linked list (n^5).  The reason it was so inefficient is because he didn't walk to the next node in those linked lists - he started over at the beginning each time.  Which Big-O helps analyze awesomely  

---

### Answer by username_11 on 2018-03-27. Score: 5

I learned to program a long time before I'd ever *heard* of "Big O Notation" or any other formal analysis of algorithms, asymptotic or otherwise. Three plus decades into my programming, I read a book by [Clifford A. Shaffer](https://www.cs.vt.edu/user/48 "Professor Clifford A. Shaffer") of [Virginia Tech](https://vt.edu/), *[A Practical Introduction to Data Structures and Algorithm Analysis](https://rads.stackoverflow.com/amzn/click/B007EID7AQ)*. It has since been republished as *Data Structures and Algorithm Analysis* with version in [C++](https://rads.stackoverflow.com/amzn/click/048648582X) and [Java](https://rads.stackoverflow.com/amzn/click/0486485811).
Both the [C++ version](https://drive.google.com/open?id=1b18p0Zd4jbRxXQ1tebTmzLsdEDBcEEkH) and [Java version](https://drive.google.com/open?id=1zjF5kdOd9iKxzaHIT_FXo4HZw4s7-1EO) are available [online](https://people.cs.vt.edu/shaffer/Book/) along with lots all of the [resources](https://people.cs.vt.edu/shaffer/Book/JAVA/CS3114_09212011.ppt "Download the PowerPoint presentation"), [assignments](https://people.cs.vt.edu/shaffer/Book/Assignments.html "A collection of programming assignments that the author has used"), and [C++](https://people.cs.vt.edu/shaffer/Book/C++3e/progs) and [Java](https://people.cs.vt.edu/shaffer/Book/JAVA/progs) source codes for using the books in class.

> [![A Practical Introduction to Data Structures and Algorithm Analysis, 2nd edition](https://i.sstatic.net/4xqiYt.jpg "A Practical Introduction to Data Structures and Algorithm Analysis Second Edition")](https://books.google.com/books/about/A_Practical_Introduction_to_Data_Structu.html?id=uPwkAQAAIAAJ)    
> [![Data Structures and Algorithm Analysis in C++](https://i.sstatic.net/axbBat.jpg "Data Structures and Algorithm Analysis in C++ Third Edition")](http://store.doverpublications.com/048648582x.html)    
> [![Data Structures and Algorithm Analysis in Java](https://i.sstatic.net/gazdrt.jpg "Data Structures and Algorithm Analysis in Java Third Edition")](http://store.doverpublications.com/0486485811.html)

When I first read chapter 3, *Algorithm Analysis*, I basically said to myself, "Yeah, I got that." After all, I'd been programming for a while, and I had a good *sense* about how complex an algorithm was, and didn't need any formal notation, or explanation for it. Later, after it had percolated through my brain for a while, I realized that it *was* rather handy to have a way to explain to others, including customers and managers, why doing it *this* way would take more time, even if it saved disk space, or, on the other hand, why *that* way was doing the job fast, but the disk access was the bottleneck in program speed. All I could remember from the first breeze through the chapter was that it had a lot of mathematics involved, including things like $O(n log n)$, $T(n)=O(f(n))$, and such. I knew I'd seen at least one $\sum\_{i=0}^n = yada + yada$ type expression in there somewhere as well.

Never having studied Calculus I was rather intimidated by the thought of all that math. (I like math pretty well, and I also know what I don't know.) Still, I had the book and I had the time, so it couldn't hurt to go back and *study* that chapter again. On the second reading I realized that while there was math *involved*, there wasn't really any math *performed*. Rather the concepts of math were used to *explain* what was being analyzed and how that affected teh growth rate. The concepts were important, but never once did an equation need to be *solved*. Furthermore, just in case the student did not understand the relationships between $10n$, $n log n$, $n^2$, $2^n$, and $n!$ the author included graphs and tables.

> [![Sample graph](https://i.sstatic.net/cqLCvl.png)](https://i.sstatic.net/cqLCv.png)
>
> [![Sample table](https://i.sstatic.net/Bg1KPl.png)](https://i.sstatic.net/Bg1KP.png)

The language of the books is aimed at college-level students, and the equations and explanations seem to assume the student has a prior understanding of the "language" used in the mathematical analysis. Therefore, I couldn't recommend using that as the textbook for the class, or even for that segment of class. I can, however, recommend it as an excellent starting point for *your* lesson plan. Using the progression of his explanations for *finding* the growth rate of an algorithm, you can rework the examples, and the application of mathematical *concepts* so that it better fits the knowledge of your students, and carry it forward in a manner consistent with your style in the class so far. The method used to show, and find, growth rates, and the Big $\Bbb O$, Big $\Omega$, and Big $\Theta$ are decidedly *non-math* in their application, and adjusting the material for the students you see in your classroom should be reasonably simple.

I agree that you should give your students the exposure to the subject, and deepen that exposure as much as the curriculum will allow. I've found, after learning from that chapter, that I am equipped to explain my analysis of a routine, and its possible optimizations, much better to other programmers - whether they know Big $\Bbb O$ notation or not. If someone *does* know Big $\Bbb O$, it is an excellent shortcut to explaining why a routine is slow, and if they *do not* know Big $\Bbb O$, I am now able to quantify and explain what I used to intuit and couldn't explain.

### The *Mathematics* Involved

Again, the mathematics is more for explaining the results than for finding them. Understanding what the graph looks like helps a lot, by orders of magnitude. The online [graphing calculator](https://www.desmos.com/calculator) mentioned by [username_9](https://cseducators.stackexchange.com/users/1293/buffy) in another [answer](https://cseducators.stackexchange.com/a/4555/104) is an excellent way to deal with the math involved in understanding the *growth rate* that Big $\Bbb O$ notation signifies. I once made a similar, if *much* simpler, tool for explaining the concepts of linear, logarithmic, and quadratic to GED students. What they couldn't grasp with words and text, the readily apprehended with interactive visuals.

### The Testing

As this will be the introduction to Big $\Bbb O$ notation, and at that only a "dip your toe in the water" type exposure, testing on the subject probably shouldn't be very intense. If you covered the complexity of heap sort and can write a heap sort in a manner they have not seen, then use that and ask them to find the Big $\Bbb O$ of the new version. It's still a heap sort, and they should be able to reach the same results as for the one they've already seen. Additionally, with some short code fragments, have them classify the fragments, or use pairs or fragments, and ask for the one with the better Big $\Bbb O$ for a significantly large value of $n$. The idea is to reinforce the usefulness of the analysis, and that Big $\Bbb O$ notation is only a simple, common, way of expressing the complexity that allows for comparing algorithms and selecting which one to use in a new situation. Leave the finer details for later courses when, and if, they pursue a CS curriculum.

> **Comments:**
> **username_12**: While drawing asymptotic behaviour is fine, you should be careful to include that making an asymptotic claim from a drawing is a dangerous exercise that shouldn't be attempted unless the student knows what that means!  
> **username_13**: In the table of results, I would add a sample how the time grow for each complexity. For instance base the fact that at n=100 O(n) take 1s and show us the time that it represent, people will understand that much better.  

---

### Answer by username_14 on 2018-03-27. Score: 4

Teach it as a pure concept and not as a mathematical formula. Big O simply describes how your algorithms runtime behaves as your data increases.

Let's say you are looking for a certain item out of a pile of 10 items. Let's look at an algorithm which is essentially "pick up each item and check it, and set it aside if it isn't the one and keep picking". That algorithm may be fine and perform within a runtime that meets expectations, but as the number of items in the pile increases, the runtime does too. If the number of items increases to billions, the runtime may become unacceptable.

In this example, the Big O is basically linear. As the number of items increases the runtime increases in a linear fashion. It is important to understand the Big O of your algorithm from the start because that can help you avoid starting out with a bad algorithm.

To illustrate that, now consider that we started with an algorithm that just inspects one item, checks to see if it is the one and if not throw it back into the pile, then repeat. In other words, we don't set the ones we know aren't the item aside. Now our algorithm is very inefficient and has an exponential Big O because there is potential to inspect items more than once. It could also happen that the algorithm never finishes at all, and the likelihood of that happening increases as the number of items gets humongous.

If we happened to start with that idea, and pause to understand the Big O, we'd have started with the better algorithm. Searches of unmanaged data should be linear, meaning the worst scenario in searching n items is that you have to pick and examine all n items.

Now you move into ways we get better than linear performance. If you have control over how the pool of items you will search is organized, and you can insert them in a sorted fashion, then your search can be better than linear.

Or, if you take the time to index the items, your algorithm can be much better than linear. A good example is a library -- books are arranged by section, then by author. You don't have to search every book in the library to find the one you seek. The library also has a card catalog, so you don't have to search at all.

But there is work/time involved in organizing and maintaining the library and its catalog. But it makes sense to accept this overhead because the volume of books that come in is much, much lower than the volume of searches. It also takes space. An organized library has a larger physical footprint than it would have if the books were not organized for better searching. The card catalog takes space too.

A computer scientist weighs all the constraints and device the best strategy. Any algorithm for searching that is better than linear will slow down the additions and changes of items into the pool. If the items are added/removed/changed a lot more frequently than they are searched, then an index search may not be a good choice.

I would expect high school students that understand these concepts to be able to answer questions on a test that propose a search algorithm, and provide the key constraints, and ask "is this a good strategy?" or "how might this strategy be improved and what down-sides should be considered?"

When you can ignore the overhead that inserting/updating the data in an organized (or even indexed) fashion then it makes sense to target a better than linear approach. But when you can't ignore that because the volume of add/delete/updates is huge, and cannot be slowed down, then it makes sense to target a linear approach.

I'd expect junior computer science students to be able to understand the considerations and make choices and explain their choice. If they can do that but cannot necessarily express it in formal mathematical language, I'd be OK with that. But as an educator you would need to align to whatever your district/state expects, because if ultimately then end up taking a standardized test that does not focus on concepts and does focus on mathematical formulas, that would not work.

If your school aligns to the below, then what I describe above would work:

<https://k12cs.org/framework-statements-by-concept/#jump-algorithms-programming>

Because as 12th grade student:

"Analysis using sophisticated mathematical notation to classify algorithm performance, such as Big-O notation, is not expected."


---

### Answer by username_12 on 2018-03-26. Score: 3

What I always do is to look at multiplying by $2$, as everyone can multiply by $2$.

Consider $O(n)$ (linear) time, if you double $n$, then the running time doubles\* (okay, not precisely, I'm assuming $c\cdot n$ here. But this is a preparation, let's just assume we have only the leading term. If you think this is important, add this)

Now look at $O(n^2)$ (quadratic), here doubling $n$ gives us a running time of $4$ times the original! Wow! This isn't fun!

Now, bonus, consider $O(2^n)$ and lets multiply by $2$ again! Uh oh. The answer now is $2^n$ times longer than before. This is bad! Let's stick to polynomial running times!

Oh and this works with $O(1)$ as well. What happens if I double $n$? Nothing! It remains $O(1)$!

> **Comments:**
> **username_0**: Funny you should mention this.  A student came to me yesterday during lunch and did the very same analysis on the board to make sure she understood the concept.  
> **username_12**: @JavaJive This is so simple that everyone can think of it. That alone already makes it useful for teaching, IMO.  

---

