Thursday, March 17, 2005

Politics-Oriented Software Development

Documentation is an essential tool in the twin goals of ass-covering and of managing management...strike the correct tone of opaque vagueness and unshakeable authority.

A kind of funny (but cynical) article about Politics-Oriented Software Development.

Sunday, March 06, 2005

Inversions

Given a sequence x1, x2, ... xn, we say that the pair 1 &le i < j &le n is an inversion if xi > xj.

Now, given a sequence sequence S = x1, x2, ... xn, how efficently can you count the total number of inversions in S?

For example, if S = 1, 5, 4, 3 then S has 3 inversions - the pairs (5, 4), (5, 3), and (4, 3).

The straightforward algorithm is the compare all pairs of elements in S, which has a O(n2) runtime.

A better algorithm is to modify the merge sort algorithm to count the inversions that it undoes while sorting S. This yields an O(nlogn) algorithm.

Is O(nlogn) the best possible? That is, is counting inversions also &Omega(nlogn)? (This is true for (comparision-based) sorting, but one does not necessarily need to sort to S to count the total number of inversions).