5 comments

  • qsort58 minutes ago
    I think the confusion is because strictly speaking $f(x) = O(g(x))$ is an abuse of notation. $O(g(n)), \Theta(g(n))$ and friends are sets. We can&#x27;t say that a function equals a set, or that a function &quot;is less&quot; than another function, but notoriously mathematics runs on javascript, so we try to do something instead of giving a type error.<p>Here &quot;is less&quot; is interpreted as &quot;eventually less for all values&quot; and &quot;plus a set&quot; is interpreted as &quot;plus any function of that set&quot;.<p>I never liked this notation for asymptotics and I always preferred the $f(x) \in O(g(x))$ style, but it&#x27;s just notation in the end.
    • ndriscoll28 minutes ago
      To me it seems similar to the + C on an antiderivative (or more generally, quotient objects). Technically, you are dealing with an equivalence class of functions, so a set. But it&#x27;s usually counterproductive to think of it that way (and when you study this stuff properly, one of the first things you do is prove that you (usually) don&#x27;t need to, and can instead use an arbitrary representative as a stand-in for the set), so you write F(x)+C.
      • qsort11 minutes ago
        I think the Landau notation is a bit more finicky with the details. When it&#x27;s really a quotient (like modular arithmetic) I&#x27;m with you, but here $O()$ morally means &quot;at most this&quot; and often you have to use the &quot;direction of the inequality&quot; to prove complexity bounds, so I&#x27;m more comfortable with the set notation. But again, it&#x27;s just notation, I could use either.
    • hyperpape37 minutes ago
      Although, when I learned foundations of mathematics, every function was a set, and if you wanted them, you&#x27;d get plenty of junk theorems from that fact.
      • qsort31 minutes ago
        &quot;Everything is an object&quot; is for boys, &quot;everything is the empty set composed with copies of itself via the axiom of pairing&quot; is for men ;)
    • foxes21 minutes ago
      I feel its not that bad an abuse of notation as kinda consistent with other areas of mathematics -<p>A coset, quotients r + I, affine subspaces v + W, etc. Not literal sets but comparing some representative with a class label, and the `=, +` is defined not just on the actual objects but on some other structure used to make some comparison too.
  • josalhor1 hour ago
    &gt; computer science students should be familiar with the standard f(x)=O(g(x)) notation<p>I have always thought that expressing it like that instead of f(x) ∈ O(g(x)) is very confusing. I understand the desire to apply arithmetic notation of summation to represent the factors, but &quot;concluding&quot; this notation with equality, when it&#x27;s not an equality... Is grounds for confusion.
    • FartyMcFarter39 minutes ago
      Given this possible confusion, is it still valid to say the following two expressions are equivalent as the article does?<p>f(x) = g(x) + O(1)<p>f(x) - g(x) = O(1)
  • dataflow4 minutes ago
    [delayed]
  • edflsafoiewq11 minutes ago
    O(1) just means &quot;a bounded function (on a neighborhood of infinity)&quot;. Unlike f(x), which refers to some function by name, O(1) refers to some function by a property it has. It&#x27;s the same principle at work in &quot;even + odd = odd&quot;.<p>Programmers wringing their hands over the meaning of f(x)=O(g(x)) never seem to have manipulated any expression more complex than f(x)=O(g(x)).
  • jheriko36 minutes ago
    [dead]