ln n!

In the course of analyzing an algorithm, I used the simplifying hypothesis that the cost function is

.

That expression is cumbersome but we can get a really good simplified function to use as a proxy. Let’s see how.

Rotating Arrays (part II)

Last week we had a look at Kernighan’s algorithm to rotate an array position and concluded that it might not be optimal, as each element was moved twice. This week, we’ll have a look at another algorithm that moves some items more than once, but overall will do less than two exchanges per items.

Rotating Arrays (Part I)

To “rotate” an array position to the left (or to the right, doesn’t really matter) we could repeat times a shift of one, using only one temporary variable. This method doesn’t use much auxiliary memory but is inefficient: it will do copies if we apply it to an array of size . Surely we can do better.

Selection, Revisited.

When we think of searching, we generally think of searching a value in a sorted collection of some sort. For a simple array, this implies the array is sorted and that we use binary search or a variant. But what if we want to search by rank? In a sorted array, that’s not very hard: the th item is in slot . But what if the array is not sorted?