5 ms·

What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics

42 points by ibobev 9mo ago

josalhor 8mo ago
> computer science students should be familiar with the standard f(x)=O(g(x)) notation 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 "concluding" this notation with equality, when it's not an equality... Is grounds for confusion.
- FartyMcFarter 8mo ago
  Given this possible confusion, is it still valid to say the following two expressions are equivalent as the article does? f(x) = g(x) + O(1) f(x) - g(x) = O(1)
  - jibal 8mo ago
    f(x) - g(x) ∈ O(1)
- NooneAtAll3 8mo ago
  you're confused because it isn't a set it's a notation for "some element of that set"
qsort 8mo 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't say that a function equals a set, or that a function "is less" than another function, but notoriously mathematics runs on javascript, so we try to do something instead of giving a type error. Here "is less" is interpreted as "eventually less for all values" and "plus a set" is interpreted as "plus any function of that set". I never liked this notation for asymptotics and I always preferred the $f(x) \in O(g(x))$ style, but it's just notation in the end.
- foxes 8mo ago
  I feel its not that bad an abuse of notation as kinda consistent with other areas of mathematics - 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.
  - mathgradthrow 8mo ago
    No. Equality is defined on sets, with exactly one exception, this stupid fucking notation.
    - foxes 8mo ago
      Notation is invented to be useful. A lot of mathematicians and physicists write stuff like f = g + O(h) and then proceed to do a bunch of manipulations without getting bogged down in set theory syntax. Also equality isnt just defined on sets, usually people start by defining it as like a formal thing satisfying a bunch of rules as a part of their logic, and going from there.
      - mathgradthrow 8mo ago
        Equality is defined on sets. Everything is a set. Equality means equalty as sets. That's how math aorks unless you're doing type theory shit.
- hyperpape 8mo ago
  Although, when I learned foundations of mathematics, every function was a set, and if you wanted them, you'd get plenty of junk theorems from that fact.
  - qsort 8mo ago
    "Everything is an object" is for boys, "everything is the empty set composed with copies of itself via the axiom of pairing" is for men ;)
jheriko 8mo ago
[dead]
edflsafoiewq 8mo ago
O(1) just means "a bounded function (on a neighborhood of infinity)". Unlike f(x), which refers to some function by name, O(1) refers to some function by a property it has. It's the same principle at work in "even + odd = odd". 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)).
- ajkjk 8mo ago
  I think this is the best interpretation. It is not different than writing $r+I$ for a coset.
deleted 8mo ago
[deleted]
bo1024 8mo ago
The easiest way to read it is "there exists a function h in O(1) such that f(x) <= g(x) + h(x)." I think first we should teach "f in O(g)" notation, then teach the above, then observe that a special case of the above is the "abuse of notation" f(x) = O(g(x)).
dataflow 8mo ago
Maybe an easier explanation: just subtract g(x) from both sides. You get: f(x) - g(x) ≤ O(1) Now, if you already know that f(x) - g(x) = O(1) means "f and g eventually differ by no more than a constant", then f(x) - g(x) ≤ O(1) must mean "f eventually stops exceeding g by a constant".
tokenless 8mo ago
You do things a bit different on an actual computer, right. As x cannot tend to infinity (so everything is O(1) by that measure) so common sense is applied.
- groundzeros2015 8mo ago
  Complexity theory studies inherent growth in problems, not bound to a particular machine
nicggckgcbnn 8mo ago
[dead]

42 points by ibobev 9mo ago

> computer science students should be familiar with the standard f(x)=O(g(x)) notation 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 "concluding" this notation with equality, when it's not an equality... Is grounds for confusion.

FartyMcFarter 8mo ago
Given this possible confusion, is it still valid to say the following two expressions are equivalent as the article does? f(x) = g(x) + O(1) f(x) - g(x) = O(1)
- jibal 8mo ago
  f(x) - g(x) ∈ O(1)
NooneAtAll3 8mo ago
you're confused because it isn't a set it's a notation for "some element of that set"

qsort 8mo 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't say that a function equals a set, or that a function "is less" than another function, but notoriously mathematics runs on javascript, so we try to do something instead of giving a type error. Here "is less" is interpreted as "eventually less for all values" and "plus a set" is interpreted as "plus any function of that set". I never liked this notation for asymptotics and I always preferred the $f(x) \in O(g(x))$ style, but it's just notation in the end.

foxes 8mo ago
I feel its not that bad an abuse of notation as kinda consistent with other areas of mathematics - 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.
- mathgradthrow 8mo ago
  No. Equality is defined on sets, with exactly one exception, this stupid fucking notation.
  - foxes 8mo ago
    Notation is invented to be useful. A lot of mathematicians and physicists write stuff like f = g + O(h) and then proceed to do a bunch of manipulations without getting bogged down in set theory syntax. Also equality isnt just defined on sets, usually people start by defining it as like a formal thing satisfying a bunch of rules as a part of their logic, and going from there.
    - mathgradthrow 8mo ago
      Equality is defined on sets. Everything is a set. Equality means equalty as sets. That's how math aorks unless you're doing type theory shit.
hyperpape 8mo ago
Although, when I learned foundations of mathematics, every function was a set, and if you wanted them, you'd get plenty of junk theorems from that fact.
- qsort 8mo ago
  "Everything is an object" is for boys, "everything is the empty set composed with copies of itself via the axiom of pairing" is for men ;)

jheriko 8mo ago

[dead]

edflsafoiewq 8mo ago

O(1) just means "a bounded function (on a neighborhood of infinity)". Unlike f(x), which refers to some function by name, O(1) refers to some function by a property it has. It's the same principle at work in "even + odd = odd". 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)).

ajkjk 8mo ago
I think this is the best interpretation. It is not different than writing $r+I$ for a coset.

deleted 8mo ago

[deleted]

bo1024 8mo ago

The easiest way to read it is "there exists a function h in O(1) such that f(x) <= g(x) + h(x)." I think first we should teach "f in O(g)" notation, then teach the above, then observe that a special case of the above is the "abuse of notation" f(x) = O(g(x)).

dataflow 8mo ago

Maybe an easier explanation: just subtract g(x) from both sides. You get: f(x) - g(x) ≤ O(1) Now, if you already know that f(x) - g(x) = O(1) means "f and g eventually differ by no more than a constant", then f(x) - g(x) ≤ O(1) must mean "f eventually stops exceeding g by a constant".

tokenless 8mo ago

You do things a bit different on an actual computer, right. As x cannot tend to infinity (so everything is O(1) by that measure) so common sense is applied.

groundzeros2015 8mo ago
Complexity theory studies inherent growth in problems, not bound to a particular machine

nicggckgcbnn 8mo ago

[dead]