Hi! First, hopefully this is my last for this weekend ;-) And subject was a little cheating because the O(n^2) prepare part still exists, but the core part now O(n+e) where e is the number of depends which is usually O(n), so the core algorithm is about O(n) now. Here is the little patch: ------------------------- diff -Naur pacman-lib/lib/libalpm/deps.c pacman-lib.new/lib/libalpm/deps.c --- pacman-lib/lib/libalpm/deps.c 2007-04-22 19:46:40.000000000 +0200 +++ pacman-lib.new/lib/libalpm/deps.c 2007-04-22 19:46:09.000000000 +0200 @@ -69,9 +69,10 @@ pmgraph_t *_alpm_graph_finduntouched(alpm_list_t *vertices) { - alpm_list_t *i; + static alpm_list_t *i = NULL; + if (!i) i = vertices; pmgraph_t *found = NULL; - for (i = vertices; i && !found; i = i->next) { + for (; i && !found; i = i->next) { pmgraph_t *vertex = i->data; if (vertex->state == 0) found = vertex; } -------------------------- Enjoy, ngaba