5 ms·

What is O(1000) satellites?

oh_sigh 8y ago
It's borrowed from comp sci, but you can read O(x) as "on the order of x", so maybe 900, maybe 1200, but somewhere around there.
- loeg 8y ago
  In Comp Sci O() notation has a very specific meaning and "on the order of" does not approximate it. I think it was probably just a misuse of the notation.
  - gameswithgo 8y ago
    "The letter O is used because the growth rate of a function is also referred to as the order of the function" order of...order of yeah I know there is no "growth"
    - loeg 8y ago
      You've taken an informal and sloppy summary of big-O notation, isolated a single English expression, and construed that a similar English expression used in a different context with entirely different meaning is an accurate approximation of the formal meaning. You would be incorrect.
  - rak00n 8y ago
    I have seen it getting used in many places and it's understood as order of. O(n) means at worst case number of steps needed to complete an algorithm would be c.n + a. So it is completely valid use since O(1000) would mean it can be c.1000 + a, which actually means order of 1000s.
    - loeg 8y ago
      This is also an inaccurate description of the property O().
      - rak00n 8y ago
        How so? https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation https://www.khanacademy.org/computing/computer-science/algor...
        loeg 8y ago
        https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation > Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. I.e., it's an asymptotic upper bound. It's also interesting to compare with Ω() (Big Omega — asymptotic lower bound) and Θ() (Big Theta) (big-O AND big-Omega): https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm... A good textbook on this subject is Introduction to Algorithms: https://www.amazon.com/dp/0262033844/ https://www.amazon.com/dp/0262033844/ .
        rak00n 8y ago
        What I described is the same thing in layman's term. Worst case is the colloquial word for upper bound. And in that example n was approaching 1000. If you want to be puritan the only fault I see in my definition is instead of using a generic function I assumed it's linear function - but that's for explaining the colloquial use.
        repsilat 8y ago
        It's just an asymptotic upper bound (though often used to imply tight bounds). It's most commonly applied to worst case running time, but is often applied to expected running time ("hash table insertions run in O(1)"), space complexity, communication overhead, numerical accuracy and any number of other metrics.
  - repsilat 8y ago
    In informal contexts it's also used as a fudge/handwave, purely as a questionable analogy that nobody is expected to take too seriously. `theptip` almost certainly knows that O(1000)=O(1), they were just being playful.
    - loeg 8y ago
      Exactly.
  - oh_sigh 8y ago
    I guarantee you can find dozens of examples of CS-type people using O() in non-algorithmic-complexity topics as "on the order of" or "approximately" right here on HN within the past 6 months. They aren't all misusing that notation - it is being co-opted into a more general lexicon, whether you like it or not. And I wasn't saying that "on the order of" is an approximation of what O() actually is in CS, merely that that is how OP used it.
spiderPig 8y ago
It's an unnecessary misuse of the Big O notation used to establish bounds of functions. I think they just meant up to 1000 satellites
loeg 8y ago
The author means literally 1000 satellites.

It's borrowed from comp sci, but you can read O(x) as "on the order of x", so maybe 900, maybe 1200, but somewhere around there.

loeg 8y ago
In Comp Sci O() notation has a very specific meaning and "on the order of" does not approximate it. I think it was probably just a misuse of the notation.
- gameswithgo 8y ago
  "The letter O is used because the growth rate of a function is also referred to as the order of the function" order of...order of yeah I know there is no "growth"
  - loeg 8y ago
    You've taken an informal and sloppy summary of big-O notation, isolated a single English expression, and construed that a similar English expression used in a different context with entirely different meaning is an accurate approximation of the formal meaning. You would be incorrect.
- rak00n 8y ago
  I have seen it getting used in many places and it's understood as order of. O(n) means at worst case number of steps needed to complete an algorithm would be c.n + a. So it is completely valid use since O(1000) would mean it can be c.1000 + a, which actually means order of 1000s.
  - loeg 8y ago
    This is also an inaccurate description of the property O().
    - rak00n 8y ago
      How so? https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-o-notation https://www.khanacademy.org/computing/computer-science/algor...
      - loeg 8y ago
        https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation > Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. I.e., it's an asymptotic upper bound. It's also interesting to compare with Ω() (Big Omega — asymptotic lower bound) and Θ() (Big Theta) (big-O AND big-Omega): https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachm... A good textbook on this subject is Introduction to Algorithms: https://www.amazon.com/dp/0262033844/ https://www.amazon.com/dp/0262033844/ .
        rak00n 8y ago
        What I described is the same thing in layman's term. Worst case is the colloquial word for upper bound. And in that example n was approaching 1000. If you want to be puritan the only fault I see in my definition is instead of using a generic function I assumed it's linear function - but that's for explaining the colloquial use.
      - repsilat 8y ago
        It's just an asymptotic upper bound (though often used to imply tight bounds). It's most commonly applied to worst case running time, but is often applied to expected running time ("hash table insertions run in O(1)"), space complexity, communication overhead, numerical accuracy and any number of other metrics.
- repsilat 8y ago
  In informal contexts it's also used as a fudge/handwave, purely as a questionable analogy that nobody is expected to take too seriously. `theptip` almost certainly knows that O(1000)=O(1), they were just being playful.
  - loeg 8y ago
    Exactly.
- oh_sigh 8y ago
  I guarantee you can find dozens of examples of CS-type people using O() in non-algorithmic-complexity topics as "on the order of" or "approximately" right here on HN within the past 6 months. They aren't all misusing that notation - it is being co-opted into a more general lexicon, whether you like it or not. And I wasn't saying that "on the order of" is an approximation of what O() actually is in CS, merely that that is how OP used it.

spiderPig 8y ago

It's an unnecessary misuse of the Big O notation used to establish bounds of functions. I think they just meant up to 1000 satellites

loeg 8y ago

The author means literally 1000 satellites.