Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Sebastian S. <seb...@gm...>]

On Fri, Nov 19, 2010 at 11:28 PM, Fabian Giesen <ry...@gm...> 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