'just complexity' problems

I've always found a fun example to be the naive (recursive) implementation of fibonacci, because you can write it in front of the students, run it for 3 and 5 so they can verify that it works, then run it for 21 and let it run in the background for 10 minutes or so while you lecture.

Then you can use the dynamic programming approach, and suddenly you have a very motivated, even emotionally resonant, rationale for a discussion about runtime.

What I've never managed to pull off, but would be very effective if I could find a topic, is to talk about something else while that program just keeps running. When it stops, I would use that as the trigger to turn back to the Fibonacci algorithm.

"Ah, I see it has finally finished! Why did it take so long?"

And this would inevitably lead to, "is there some way we can do better?"

And that would lead really nicely into big O.

When I talk about complexity, I work with three examples:

1. Summation: I implement the summation from $1$ to $n$ using a for loop, obtaining an algorithm that is $O(n)$, then I algebraically obtain the formula for the sum of the terms of an arithmetic progression of ratio 1: $\sum_1^n = \frac{n(n+1)}{2}$ which is $O(1)$;

2. Two-Sum and Three-Sum: I implement using sequential search, obtaining respectively $O(n^2)$ and $O(n^3)$ and then applying binary search, obtaining respectively $O(n \log_2 n)$ and $O(n^2 \log_2 n)$;

3. Union-Find: I present the problem of dynamic connectivity and implement QuickFind, QuickUnion and WeightedQuickUnion. I apply the implementations in a visual simulation for the percolation problem. A reference is this one https://algs4.cs.princeton.edu/15uf/

The percolation simulator can be found here: https://github.com/davidbuzatto/Percolacao

Please note that the purpose of the simulation is only to show how fast the water percolates, i.e. connects the upper medium to the lower medium according to the algorithms used to implement each data structure operations. To show the difference in performance, you should change the simulation parameters and vary the algorithms. The simulation itself is not very accurate, since the percolating water should not "rise" in the percolating material, but this can be ignored, since the purpose is really to show that QuickFind is very slow compared to WeightedQuickUnion. This "error" is evident in the lower left quadrant. You can correct it if you wish. Furthermore, the simulator is implemented in Java and the comments and program elements are in Brazilian Portuguese.