ln n!

23/02/2016

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

$\displaystyle c(n)\approx\sum_{i_1}^n \lg i=\lg n!$.

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)

16/02/2016

Last week we had a look at Kernighan’s algorithm to rotate an array $k$ 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)

09/02/2016

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

Selection, Revisited.

02/02/2016

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 $k$th item is in slot $k$. But what if the array is not sorted?