How do you teach Big O to high schoolers with varying degrees of math exposure?

Question

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?

Answer 1

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

Answer 2

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 T_walk(N) = (1/speed)*N; when we remove the constant (1/speed), this function is just O(N). The horizontal line represent the function T_teleport(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 T_walk(N) = (1/speed)*N or (1/speed)*N + 60 or T_walk(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).

Answer 3

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(n²) to O(n⁵). 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:

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

Answer 4

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 of Virginia Tech, A Practical Introduction to Data Structures and Algorithm Analysis. It has since been republished as Data Structures and Algorithm Analysis with version in C++ and Java. Both the C++ version and Java version are available online along with lots all of the resources, assignments, and C++ and Java source codes for using the books in class.

         

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.

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 mentioned by Buffy in another answer 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.

Answer 5

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 6

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)$!