`On Sun, 2005-06-05 at 09:58 +0200, Esben Nielsen wrote:> On Sun, 5 Jun 2005, Thomas Gleixner wrote:> > > [...] > >   *> >   * Based on simple lists (include/linux/list.h).> > @@ -17,35 +22,50 @@> >   * a priority too (the highest of all the nodes), stored in the head> >   * of the list (that is a node itself).> >   *> > - * Addition is O(1), removal is O(1), change of priority of a node is> > - * O(1).> > + * Addition is O(N), removal is O(1), change of priority of a node is> > + * O(N).> >   *> > - * Addition and change of priority's order is really O(K), where K is> > - * a constant being the maximum number of different priorities you> > - * will store in the list. Being a constant, it means it is O(1).> > - *> > What is N? The number of nodes in the list or the number of different> priorities? If it is the number of nodes in total this exercise is> worthless: You could just as well have a sorted list.> > But I hope and also think that the original explanation was correct.Sorry, I meant K the number of different priorities. I just find it completely bogus, that O(K) == O(1) for any K != 1. tglx-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`