lkml.org 
[lkml]   [2005]   [Jun]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: patch] Real-Time Preemption, plist fixes
    On Sun, 5 Jun 2005, Thomas Gleixner wrote:

    > 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
    >

    When K is a constant or bounded by a constant (140 in this application)
    any function which is O(K) is O(1) per definition of O!

    Esben

    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-06-05 10:46    [W:3.721 / U:0.036 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site