[nawitus]

> ~O(1) access time

What's the difference between O(1) and ~O(1)?

[fournm]

I've seen ~O(1) as amortized constant time fairly frequently.

[mhurron]

I've always seen ~ as used for about, so ~1h is somewhere around one hour.

I would read it as close to, but maybe not quite O(1).

[msluyter]

I think the point may be that the fuzziness is already built into big-O notation. That is O(n) + C = O(n), where C is a constant.

[nawitus]

If only set notation was more common with big-O notation. 'O(n) + C = O(n)' can be confusing, whereas 'f(x) ∈ O(n) ∧ f(x) ∈ O(n) + C' makes sense.

[jlarocco]

The set notation you gave is redundant. There's always an implied "+C" in any O(...), so why waste space writing it out multiple times?

Furthermore, using precise set notation would, IMO, make it more difficult to use. A big blob of set notation would not be easy to read for most people.

[nawitus]

>The set notation you gave is redundant. There's always an implied "+C" in any O(...),

No. O(n) and O(n)+C and different sets. However, if an algorithm belongs to the first set, it also belongs to the latter. The confusion comes from using the equality sign instead of the "element of" operator.

>Furthermore, using precise set notation would, IMO, make it more difficult to use. A big blob of set notation would not be easy to read for most people.

No, the only difference is that f(x) = O(n) becomes f(x) ∈ O(n).

[jlarocco]

All big-O has an implied "+C", so O(n) is equivalent to O(n)+C by definition. Where is the confusion?

[eggnet]

If I recall correctly, more generally O(A*f(n)+B) = O(f(n)) where A and B are constant.

[nawitus]

But if an algorithm is O(0.5), then it also belongs to O(1) and O(5), e.g. the time is constant and doesn't change with the problem size.

[__alexs]

I imagine that was the intent but the idea of something that is only approximately worst case constant time is quite odd. Does that mean it's only ever so slightly O(N)? O(N/BIGNUM) Except as I understand it that would still normally be written O(N)...

[MarcusBrutus]

the tilde notation is used for functions, e.g. you can say f(n) is ~g(n) and in that context has a rigorous meaning (limit of f(n)/g(n) is 1 as n goes to positive infinity). I haven't seen it being used with orders of growth notations (O, Θ or Ω) and my guess is that's ~O(1) is undefined or somebody's just taking liberties with the notations.