Big O() notation: a couple of sources

This post contains, just for future reference, a couple of primary sources relevant to the (“Big O”) notation:

1. Some introductory words from Asymptotic Methods in Analysis by de Bruijn
2. An letter from Donald Knuth on an approach to teaching calculus using this notation.

Advertisement

Visualizing product of permutations

A simple pedagogical trick that may come in handy: represent a permutation using arrows (curved lines) from to for each . Then, the product of two permutations can be represented by just putting the two corresponding figures (sets of arrows) one below the other, and following the arrows.

Representing permutations and products of permutations.

The figure is from an article called Symmetries by Alain Connes, found via the Wikipedia article on Morley’s trisector theorem (something entirely unrelated to permutations, but the article covers both of them and more).

I’m thinking how one might write a program to actually draw these: if we decide that the “height” of the figure is some , then each arrow needs to go from some to (using here the usual screen convention of coordinate increasing from left to right, and coordinate increasing from top to bottom). Further, each curve needs to have vertical slope at its two endpoints, so that successive curves can line up smoothly. The constraint on starting point, ending point, and directions at the endpoints defines almost a quadratic Bezier curve, except that here the two directions are parallel. So it’s somewhere between a quadratic and the (usual) cubic Bezier curve, which is given by the start point, end point, and derivatives at the start and end point. (Here we only care about the direction of the derivative; we can pick some arbitrary magnitude to fix the curve: the larger we pick, the more smooth it will look at the ends, at the cost of smoothness in the interior.)

Even knowing the curve, how do we generate an image?