Messages in this thread | | | Date | Sun, 5 Jun 2005 10:42:24 +0200 (METDST) | From | Esben Nielsen <> | Subject | Re: 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/
| |