5 ms·

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

• mhurron 13y ago
  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 13y ago
    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 13y ago
      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 13y ago
        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 13y ago
          >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 13y ago
            All big-O has an implied "+C", so O(n) is equivalent to O(n)+C by definition. Where is the confusion?
            • nawitus 13y ago
              >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'.
              • jlarocco 13y ago
                > Can you state this in a mathematically precise notation? Big-O isn't meant to be precise. The entire point is to roughly describe algorithm behavior. > 'Implied +C' is pretty much nonsense. Implied +C is built in to the definition of big-O notation. As n increases towards infinity the influence of C becomes negligible, so it's left off. Read the first chapter of any algorithms book.
              • dragonwriter 13y ago
                > O(n)+C and O(n) are different sets. Yes, and no. O(n) isn't a set until you specify the limit that goes with it; for some limits O(n) is different from O(n)+C -- the latter of which is equivalent to O(n+C). However, in CS, O(n) with no specified limit refers by convention to the set O(n) as n->infinity, and O(n) as n->infinity is equal to O(n+C) as n->infinity, because the limit as n->infinity of n is equal to the limit as n->infinity of n+C.
    • eggnet 13y ago
      If I recall correctly, more generally O(A*f(n)+B) = O(f(n)) where A and B are constant.
  • __alexs 13y ago
    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)...
  • nawitus 13y ago
    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.
• fournm 13y ago
  I've seen ~O(1) as amortized constant time fairly frequently.
• MarcusBrutus 13y ago
  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.