NACHTRAG:

Christian hat mir in der Zwischenzeit gemailt, hier mit meiner Antwort

----------------------------------------------

...

Bitte genau lesen, ich _streiche_ die untersten Elemente in beide Listen,
beide sortiert und gehe linear weiter.

Bei einer geordneten Liste musst du zusaetzlich den Sortierungsaufwand
betrachten. Der ist, ich wuerde in diesem Fall sinnvollerweise Insertion Sort
benutzen, O(n^2), stabil.

Seufz, meinetwegen O(n^4), das sit hier irrelevant weil die Listen sowieso beim Zeitpunkt der Suche bereits sortiert sind. Red ich schwedisch?

O(log(n)) bräuchte ich nur zum zusätzlichen Ordnen, wenns nicht bereits
wäre.

*ROTFL* Den Algorithmus moechte ich sehen. Nein, der niedrigste Aufwand zum
sortieren ist O(n*log(n)). Kleiner kriegt mans beim besten Willen nicht.
Vergl. auch http://de.wikipedia.org/wiki/Sortieralgorithmus -- da steht der
Beweis. Den haben wir in der Vorlesung "Einfuehrung in die Informatik II"
gemacht :))

OK hirnlos falsch abgeschrieben, mea culpa ... aber wie gesagt ist Sortierung hier NICHT relevant weil ich beim Archivieren der Postings einfach die ID an die Liste anhängen möchte.

Oder plant ihr zufällige IDs einzuführen? ;)

Deswegen kostet mich der Schnitt nur O(n), Basta!

Tschau
  Rolf