(You can watch the video version of this post on YouTube.) Now, sorting takes $\Omega(n\log n)$ time, right? I mean, it’s more subtle than that, but even if we stick to a comparison and swap model, then you can do what’s called “select” or “order statistics” in linear time. That’s the problem of finding the element that, if the array were sorted, would be at a given position – it’s the element of rank $i$.…

(You can watch the video version of this post on YouTube.) Now you know what an expected value is: it’s the sum over all possible outcomes of the probability times the value (or an integral if the space continuous). There are actually some fun ways to use expected values in algorithms, but we’ll talk about that some other time. So expectation is linear, right, and this doesn’t assume independence or anything - we just have $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$, no conditions whatsoever.…

Now everybody knows big-Oh notation, right? If you study computer science you learn about it in the first year, if not the first semester. Please allow me to be pedantic for a second. First of all – and you see this a lot, to the extent that I would say this is actually accepted notation, but I will silently judge you – technically, $O(\cdot)$ is a set of functions. So if you write something like $42n^2 = O(n^2)$, well, hm, that’s a type error.…

(You can watch the video version of this post on YouTube.) Now what’s the type of a function that multiplies two integers? I would say maybe $\mathbb{Z}^2\to \mathbb{Z}$, so: ordered pair of two integers going in, one integer coming out. There’s a different way of looking at it, though. If I only give you the first argument, say “multiply by 2,” that still kind of makes sense right? It’s just that “multiply by 2” is still a function, because we’re missing the second argument – but once we get it, we can multiply it by 2.…

Now here’s kind of a funny proof. Consider a flow network where all the capacities are integer. Claim. The maximum flow in this network is integer. That’s actually fairly obvious from max flow equals min cut: the latter is clearly integer since it is a sum of capacities. How about this though. Claim. There exists a maximum flow where all the flow values are integer. That is to say, you don’t have to split flow in an optimal solution.…