Re: Acceleration Structures For Vertex Snapping

On Fri, Nov 19, 2010 at 11:28 PM, Fabian Giesen <[email protected]> wrote:

> 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)").
>

O(1) only means that "something" is bounded by some constant as n goes to
infinity, so you're both right, but you're talking about different
"somethings".

Its a good idea to specify what that "something" is, e.g. "average case
time", "worst case time", "best case time", or "amortized time". It's a
fuzzy convention, I guess, but generally people probably assume you're
talking about worst case running times if you aren't explicit about meaning
one of the others (probably because upper bounds are somewhat more
interesting for the worst cases than for the others, where Big Theta or Big
Omega are more used). Or maybe that's just me. I tend to slap a "more or
less" on there to cover my bases :-).

-- 
Sebastian Sylvan

------------------------------------------------------------------------------
Beautiful is writing same markup. Internet Explorer 9 supports
standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2 & L3.
Spend less time writing and  rewriting code and more time creating great
experiences on the web. Be a part of the beta today
http://p.sf.net/sfu/msIE9-sfdev2dev

_______________________________________________
GDAlgorithms-list mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list