ln n!

February 23, 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.

Read the rest of this entry »

Rotating Arrays (part II)

February 16, 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.

Read the rest of this entry »

Rotating Arrays (Part I)

February 9, 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.

Read the rest of this entry »

Selection, Revisited.

February 2, 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 kth item is in slot k. But what if the array is not sorted?

Read the rest of this entry »