One question left unanswered was the computational complexity of the `apply_permutation`

function.

Here it is again:

template<typename T> void apply_permutation( std::vector<T>& v, std::vector<int>& indices) { using std::swap; // to permit Koenig lookup for (size_t i = 0; i < indices.size(); i++) { auto current = i; while (i != indices[current]) { auto next = indices[current]; swap(v[current], v[next]); indices[current] = current; current = next; } indices[current] = current; } }

The outer `for`

loop runs `N` times; that’s easy to see. The maximum number of iterations of the inner `while`

loop is a bit less obvious, but if you understood the discussion, you’ll see that it runs at most `N` times because that’s the maximum length of a cycle in the permutation. (Of course, this analysis requires that the `indices`

be a permutation of 0 … `N` − 1.)

Therefore, a naïve analysis would conclude that this has worst-case running time of `O`(`N`²) because the outer `for`

loop runs `N` times, and the inner `while`

loop also runs `N` times in the worst case.

But it’s not actually that bad. The complexity is only `O`(`N`), because not all of the worst-case scenarios can exist simultaneously.

One way to notice this is to observe that each item moves only once, namely to its final position. Once an item is in the correct position, it never moves again. In terms of indices, observe that each swap corresponds to an assignment `indices[current] = current`

. Therefore, each entry in the index array gets set to its final value. And the `while`

loop doesn’t iterate at all if `indices[current] == current`

, so when we revisit an element that has already moved to its final location, we do nothing.

Since each item moves at most only once, and there are `N` items, then the total number of iterations of the inner `while`

loop is at most `N`.

Another way of looking at this is that the `while`

loop walks through every cycle. But mathematics tell us that permutations decompose into disjoint cycles, so the number of elements involved in the cycles cannot exceed the total number of elements.

Either way, the conclusion is that there are most `N` iterations of the inner `while`

loop in total. Combine this with the fixed overhead of `N` iterations of the `for`

loop, and you see that the total running time complexity is `O`(`N`).

(We can determine via inspection that the algorithm consumes constant additional space.)

## 0 comments