[Haskell-beginners] Pearls of Functional Algorithm Design - find the smallest free number

[Felipe Almeida Lessa]

So the solution works in O(n) time to find the first item ingredient
that the recipe needs but you don't have.  It works in linear time
because there are strong assumptions about what your items are, so a
pigeonhole sort [1] is used in the checklist function.

We may also relax the conditions about what the items are if we say
that we want them in Sets (from Data.Set).  Then difference [2] is
exactly what we want and gives us all the items that are missing in
O(n) time.

With a similar restriction, but using Data.Map, we can also give a
slightly generalized algorithm where there may be multiple counts of
the items (e.g. multiple TVs in the shelves).  Then differenceWith [3]
also does the hard work for us in O(n) time.

Now, relaxing the assumptions about what the items are and allowing
them to come into lists in any other, I don't if it is possible to
solve the problem in less than O(n log n) time.  It is easy to do it
in O(n log n) time if the items are instances of Ord by constructing a
Set.  I suspect this is a lower bound.  And, unfortunately, I don't
see how the Algorithm 2 could be changed in a simple way to run in O(n
log n) time.

Cheers,

[1] http://en.wikipedia.org/wiki/Pigeonhole_sort
[2] http://hackage.haskell.org/packages/archive/containers/0.4.0.0/doc/html/Data-Set.html#v:difference
[3] http://hackage.haskell.org/packages/archive/containers/0.4.0.0/doc/html/Data-Map.html#v:differenceWith

-- 
Felipe.