On Thu, Apr 13, 2000 at 11:45:51AM -0400, Joseph A. Martin wrote:
> >It has bad complexity problems. An allocation have to keep working in O(1)
> >as now.
>
> I don't think I understand. Is "It" the whole thing or the quoted
> line? What does "0(1)" mean?
O(whatever) is a notation by which you can describe how the running time of
your algorithm depends on the amount of input. Finding books in a randomly
ordered library is O(N) - if you have twice as many books to search, it will
take twice as long.
In a perfectly ordered library, the time it takes is described by O(1) - you
will always find your book in the same time. Perhaps O(sqrt(N)) would be
more appropriate, because if there are more books, you may need to walk
further before you are at the right place. The sqrt is because your library
is two dimensional.
Naive sorting is O(N^2) - which can be good or bad. With large N, it is most
surely bad. But you should know that the *actual* running time is described
by something that looks more like t= offset + alpha*O(N^2) - if offset or
alpha are large, the O(N^2) algorithm might be faster for small N.
Do yourself a favor and get the Knuth trilogy. Not meant to be read cover to
cover, but very useful none the less.
Regards,
bert hubert.
--
| http://www.rent-a-nerd.nl
| - U N I X -
| Inspice et cautus eris - D11T'95
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sat Apr 15 2000 - 21:00:21 EST