The Roots of the Equation

In my intro-level computer science class, we spent the last two weeks before break investigating sorting algorithms and search algorithms. However, because we were kinda burnt out of Java, I decided to do it computer-free. We used small decks of cards instead. To simulate the computer only comparing two values at a time (to limit the kids using their more powerful brains to speed up the process), students were only allowed to move cards that were face-up, and could only have two cards face-up at a time. The first day I had them come up with their own algorithms and count how many steps it took them, steps being flipping a card or moving a card.

In the subsequent days, I wrote up several common sorting algorithms as they would be applied to the cards. For each of them, we kept track of how many steps the process took, which was always the same for some (Selection) but we had to think about best and worst cases with the others.

We then considered how many steps they would take for 4 cards, 5, 6, 7, 8, then n. And so we wound up creating functions to represent the complexity of the algorithm. Many of these wound up being quadratic and linear functions. All of my students had previously taken Algebra and none had problems with the linear, but the quadratic functions sometimes caused problems. But we would work what exactly changes each step, find second differences, etc, to create the functions. And no one thought this was a weird place for quadratic functions to come up – it just seemed like a natural thing that arose when we started investigating the algorithms.

Below I attached the algorithms I wrote up for the sorts. Go get a set of 8 cards and try them out. Can you figure out the function? (Note: for the Worst Case of the Merge Sort and the Quick Sort, it’s a recursive function that doesn’t necessarily have a nice explicit form.)