The first C version featured a sorted array as a states collection. In order to avoid the costly operation of incrementing all the positions of the higher states by 1, whenever a new state was added, I kept a sort margin that contained several unsorted states at the end.
A new state was first added to the end of the sort margin. When
enough states were collected there, I merged the sort margin
into the main array, by using the ANSI C
qsort()
function. This entire scheme had
an acceptable running time.
Let's analyse the complexity of everything involved. Lookup can be done using a binary search on the sorted part followed by a linear search on the unsorted part. Since the unsorted part is at most a constant number of items, then going over it is O(1) and the entire operation is that of a binary search which is an O(log(n)) operation.
Assuming the number of elements collected in the sort margin is
k, then adding
k elements, would take
O(n*log(n)) time, since the function qsort()
uses Quick-Sort which has this complexity on average.[3] O(n*log(n)) divided by a constant is still O(n*log(n))
so an insertion of an element is O(n*log(n)).
The accumulative time for adding n elements is O(n2*log(n)) which is the time for insertion multiplied by n.