![]() | |||||||||||||
Messages in this thread |
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. 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 08:02 [from the cache] ©2003-2008 | |||||||||||||