[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?

[nawitus]

>All big-O has an implied "+C"

Can you state this in a mathematically precise notation?

>Where is the confusion?

The confusion comes from stateents like 'O(n)+C = O(n)', which are actually false. O(n)+C and O(n) are different sets. If a function belongs to the latter set, it also belongs to the former, but that doesn't mean they're equal.

Using the equal sign here is "abuse of notation". 'O(n)+C = O(n)' would seem to implicate that C=0, but that's untrue. C is a constant which can be non-zero. Therefore the whole statement doesn't really make sense unless we assign a new definition to the equal sign.

Using set notation solves all the confusion.

'Implied +C' is pretty much nonsense. There are an infinite number of different sets that a single function belongs to. Just because f(x) belongs to O(n) and therefore to O(n)+C doesn't mean that 'big-O implies +C'. 'big-O' doesn't imply anything like that. '+C' is just a special case, and there's an infinite number of extra 'implies'.

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