Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Fabian G. <ry...@gm...>]

On 11/19/2010 2:43 PM, Jeff Russell wrote:
> It's not *really* O(1), since you can have an arbitrary number of
> vertices in a single hash cell (worst case would be the entire mesh).
> Only perfect hashing would allow for O(1) worst case behavior.

What do you mean by "not *really* O(1)"? Big O notation just means we're 
talking about asymptotic complexity, it doesn't have to be worst-case 
(hence "expected O(1)").

 > It's
 > really O(n) worst case, but since the n is divided by such a large
 > constant in practice it is still a very fast approach.

No, that's not true. Hash tables are fast in practice because they do a 
small number of reasonably fast operations in the average case, not 
because they do a large number of operations in a magically ultra-fast 
fashion (which would be the O(N) with tiny constant that you decribe). 
Their worst-case is definitely linear and the constant isn't tiny as 
everyone who's ever used a bad hash function knows :). Worst-case and 
average-case analysis are just different things.

-Fabian