0

I have difficulty understand the O(1) notation in this formula, does it stand for a constant? Why would people use big-O notation like this?

formula

This formula comes from the paper "Balanced Allocations" by Azar et al., and this formulas is used in the abstract:

abstract

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Bloodmoon
  • 1,308
  • 1
  • 19
  • 34
  • It's hard to say without context. – woz May 08 '13 at 16:41
  • 1
    This is answered here - http://stackoverflow.com/questions/697918/what-does-o1-access-time-mean – dexterous May 08 '13 at 16:43
  • 1
    @dexterous No, it's not. The question isn't about what big-O means – SomeWittyUsername May 08 '13 at 16:47
  • @icepack It's not the most _helpful_ answer, but that's actually exactly what the question is. Isn't OP just confused about what the definition of Big-Oh notation is? That SO post answers it. If he did understand the definition then there would be no question here. – rliu May 08 '13 at 19:57
  • 2
    @roliu- I don't think the OP is confused about the definition of big-O notation as applied to algorithms as much as the use of the terminology "f(n) + O(n)," which is not commonly encountered in basic algorithmic analysis. – templatetypedef May 08 '13 at 19:58

2 Answers2

4

Here, the term O(1) means "some term that is O(1)," meaning some term that as n goes to infinity is bounded from above by some constant. For example, it might be 137, or sin n, or 1 / n2. The value described therefore might be ln ln n / ln 2 + 137, or ln ln n / ln 2 + sin n, etc.

This use of big-O notation is common in formal mathematics when discussing low order terms in a formula that contribute a small amount to the overall total. The authors could have also written that the entire expression is O(ln ln n), but this is less precise than ln ln n / ln 2 + O(1) because it obscures the fact that the coefficient on the ln ln n is 1 / ln 2 and that the only low-order growth term is bounded from above by a constant. By explicitly writing out " + O(1)", the authors are able to give much better precision.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

Yes, O(1) means constant. The exact value of the constant isn't specified but it's probably not important for the given expression. Such notions are normally used as an intermediate step in a calculation and it removes calculation of unimportant details.

Read this expression as follows: the execution takes lnlnn/ln2 time with some constant addition. Summing this up results in O(lnlnn). Replacing O(1) with exact expression wouldn't change this result so it's ok to use approximation in the form of O(1).

SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
  • I updated my question. In fact, it is not about the execution time of a program, but an upper bound of the number of balls in a bin. So the O(1) matters a lot, and I don't know how to under stand. – Bloodmoon May 08 '13 at 17:01
  • 3
    O(1) does not mean "constant." It means "something bounded from above by a constant as n goes to infinity." – templatetypedef May 08 '13 at 17:42
  • @Bloodmoon You haven't specified it so I assumed you're talking about time. But it doesn't change the concept - in your case the resource is number of balls instead of time – SomeWittyUsername May 08 '13 at 18:26
  • @templatetypedef Formally speaking, correct. But there is no contradiction - O(1) is replaceable with that bounding constant - if we're talking in terms of big-O the result will be the same. Hope my answer is clearer now – SomeWittyUsername May 08 '13 at 18:29