I prefer being precise with terminology, sometimes to the point of annoying others.¹¹ I have learned recently that this is a general trait among hackers, which is interesting. So here’s a list of good words to know, if you, too, want to be precise.

I’ll start with just a few and then expand on it as I go, when I remember to. Actually, the primary reason I’m writing it now is that I always forget pathological, but now I have it written down!

Amortized analysis

Figuring out the average performance of an algorithm when it is run a bunch of times, instead of just once²² This is an important distinction. Some algorithms, like for example quicksort, is generally only run once. Others, like inserting an element into a hashtable, is generally run many times in sequence.. This is interesting because some algorithms are designed such that when they are run over and over, it is impossible for them to exhibit worst-case performance each time; often they are designed such that the worst case only happens very rarely, and then we want to know that when comparing it to similar algorithms.

Continuous

Smooth; ongoing. Opposite of discrete.

Deterministic

Not random; running with the same inputs gives you the same outputs; independent of time or other hidden variables.

Dirac delta function

The not-quite-actually-a-function \(\delta(x)\) can be intuitively be thought of as having value 0 everywhere except in one point: when \(x=0\). At that point, \(\delta(x)\) takes a value \(y\) that is sufficiently high to make the integral

\[\int_{-\infty}^{+\infty} \delta(x)\;\mathrm{d}x = 1.\]

In other words, the improper function \(\delta(x)\) has all of its unit area concentrated not in a tiny region, but under a single point. And because the function has unit area, all concentrated at \(x=0\), we also get (among many others) the relation

\[\int_{-\infty}^{+\infty} \delta(x) f(x)\;\mathrm{d}x = f(0).\]

This not-quite-a-function \(\delta(x)\) isn’t super easy to understand, but it has a bunch of interesting analytical properties. I mention this here mostly because I previously confused this with the Kronecker delta, but they are absolutely not the same thing, despite the similar name.

Discrete

Stepwise; jagged; cut into a finite number of pieces. Opposite of continuous.

Dynamic programming

Has nothing to do with dynamic languages or dynamic type systems.

Entropy

Concept from information theory; essentially synonymous with “how many bits are needed to reconstruct this, if trying to use as few as possible?” In other words, when you remove all redundancies, how much information remains³³ Note that this implies that a completely random string has the most information, because it cannot be generated by any other means than storing it in full.? Used when talking about compression (lower entropy means it’ll get smaller when compressed), password strength (lower entropy means it’s easier to guess), randomness (lower entropy is less random) and physical processes (lower entropy means less work, because it implies some sort of order already exists, and as long as you follow that you are being helped by the universe⁴⁴ In other words: the common saying not wanting to burn any bridges can in many cases be put more literally as wanting to maintain a low entropy or not increase entropy without good reason.).

Indicator function

See the Kronecker delta function.

Kronecker delta function

The function \(\delta(i)\) takes the value 1 when \(i = 0\), and 0 otherwise. Informally, one can also speak of the indicator function \(1_{i=0}\); these are two and the same.

This is not to be confused with the Dirac delta function (which I embarassingly did at first, but since then have fortunately been corrected by a mathematically inclined reader.)

Metasyntactic variable

A placeholder in general code examples that you’re supposed to replace with your concrete code.

Nondeterministic

Appears random. Gives different results even when run with the same inputs.

Pathological case

Evil case. Insidious input. Input that in some way triggers bad performance. A situation that leads to a known bad code path.⁵⁵ As an example of pathological input, feed a list that is sorted in reverse to the insertion sort algorithm, and you get terrible performance.