Yes: log* is to log what log is to division. In other words, it's the
number of times you have to take a logarithm before you get down to
1. It's an extremely slowly-growing function.
It's conceivable that actual, empirical time is a better metric than
asymptotic time here, because we're not really interested in what
happens as the board becomes arbitrarily large.
Peter Drake
http://www.lclark.edu/~drake/
On Jul 20, 2007, at 8:24 AM, Jason House wrote:
On 7/20/07, Peter Drake <[EMAIL PROTECTED]> wrote:
On Jul 20, 2007, at 8:04 AM, Jason House wrote:
> I thought he was using the disjoint set! I'll recheck. Well
> written disjoint sets average out to nearly O(1) operations for
> everything.
Yes -- O(log* n) to be precise, as mentioned in my book, <shameless
plug>Data Structures and Algorithms in Java</shameless plug>.
It's been a while since I was involved with theoretical analysis of
disjoint sets, but I'm fairly certain that it's faster than O(log
(n)) for some implementations. Do you mean something special by log*?
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
