Skip to main content

Bounded claims about compiled code

advanced14 min readLesson 154 of 180

Inversion counting as an optimizer-proof measurement of sorting work.

You cannot run javap in this sandbox — but you can still make bounded, honest claims about compiled code. Bubble sort's inversions (out-of-order pairs) are exactly the count of swaps it performs:

static long inversionCount(int[] a) {   // O(n^2) — honest brute force
    long inv = 0;
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] > a[j]) inv++;
    return inv;
}

inversionCount is a fact about the data; the number of swaps a correct bubble sort performs equals it exactly; and a linear scan of the final array proves the sort actually sorted (all-zero inversions). Three mutually reinforcing measurements — none of which trusts the optimizer to be honest, all of which the optimizer cannot cheat. This is the pattern for testing performance-adjacent behavior: assert on countable effects, not on vibes.