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

▲ What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics(jamesoswald.dev)

36 points by ibobev 4 days ago | 26 comments

▲ qsort 6 hours ago | parent | next [-]

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.

▲ geocar 4 minutes ago | parent | next [-]

> We can't say that a function equals a set

Why not?

Can we not so easily speak of the set of all inputs and the set of all outputs? Why not exactly then is a function not a set of morphisms/arrows?

To me, x->x+1 and {(x,x+1)|x∈R} seem the same[1]

Because it seems useful to be able to make statements of the cardinality of that set: If there are a lot of rules, then that set is big, but if there are few rules (like x->x+1), that set is small. This is enough to permit some analysis.

It also preserves "plus" for sets, because a function plus a function is the sum of those rules being considered.

What is it do you think I am missing?

[1]: I understand I don't really mean big-R here because computers have limited precision for fadd/add circuits, so if you'd prefer I said something slightly differently there please imagine I did so.

▲ sfpotter 5 hours ago | parent | prev | next [-]

The reason it's preferred to use "=" instead of "\in" is because the way that Landau notation is generally used in practice is as a kind of ellipsis or placeholder. For example, the Taylor expansion e^x = 1 + x + O(x^2). I could just as well write e^x = 1 + x + ..., but the former conveys more meaning about what is hidden behind the ellipsis. It's an abuse of notation, but in the contexts that it's used, it's not clear what additional clarity using "\in" would bring over "=". Maybe also that big O is mainly used as a notation to facilitate doing calculations, less describing what family a function belongs to. Here are Knuth's thoughts, which I agree with: https://micromath.wordpress.com/2008/04/14/donald-knuth-calc...

▲ marcosdumay an hour ago | parent [-]

You are talking about a completely different concept than the GP's.

That's why clear notation is important. Yours is kinda fine, but would be better with "≃".

	▲	Maxatar 27 minutes ago \| parent [-]
		But it's not completely different and a "≃" would not mean the same thing, in fact it would weaken the statement. e^x ≃ 1 + x + O(x^2) would only assert that lim (x->0) (e^x)/(1+x) = 1. However "e^x = 1 + x + O(x^2)" means that for some function r(x) belonging to the set O(x^2), e^x is exactly equal to 1 + x + r(x). Another way to rewrite that equation that eliminates the "abuse of notation" would be: `e^x − (1 + x) ∈ O(x^2)` The particular r(x) in O(x^2) which makes it strictly equal is being left out, that's true, and usually it's left out for brevity or practical reasons or even because it's not even be known what r(x) is... but nevertheless it is not an asymptotic equation or an approximation, it is exactly equal to the value on the right hand side for some particular r(x) the exact details of which are being omitted for one reason or another.

▲ ndriscoll 6 hours ago | parent | prev | next [-]

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'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't need to, and can instead use an arbitrary representative as a stand-in for the set), so you write F(x)+C.

▲

qsort 5 hours ago | parent | next [-]

I think the Landau notation is a bit more finicky with the details. When it's really a quotient (like modular arithmetic) I'm with you, but here $O()$ morally means "at most this" and often you have to use the "direction of the inequality" to prove complexity bounds, so I'm more comfortable with the set notation. But again, it's just notation, I could use either.

▲

ijustlovemath 5 hours ago | parent | prev [-]

Huh, never thought about the potential connection between the set-containment operation and Stokes like that.

▲

ndriscoll 5 hours ago | parent [-]

It's actually a linear (more generally, abstract) algebra thing. (All, Differentiable, Smooth, or all sorts of other sets of) functions form a vector space. The derivative is a linear operator (generalized matrix). If you have a linear equation Ax=b, then if you can find some solution X, the general solution set is X+kerA, where kerA (the kernel or nullspace) is the set of all v where Av=0. What's the kernel of the derivative operator (i.e. what has 0 derivative)? Constant functions. So the general solution is whatever particular antiderivative you find plus any constant function.

You can do this sort of "particular solution plus kernel" analysis on any linear operator, which gives one strategy for solving linear differential equations. e.g. (aD^2+bD+cI) is a linear operator (weighted sums and compositions of linear operators are linear), so you can potentially do that analysis to solve problems like af''+bf'+cf=g. In that context you say the general solution is to add a homogeneous solution (af''+bf'+cf=0) to a particular solution (my intro differential equations class covered this but didn't have linear algebra as a prereq so naturally at the time it was just magic, like everything else presented in intro diffeq).

	▲	ijustlovemath 4 hours ago \| parent \| next [-]
		Indeed, the connection to Stokes here is via the fact that both operators (abstracted derivative and antiderivative) are linear operators.
	▲	ajkjk 4 hours ago \| parent \| prev [-]
		it basically works outside of linear algebra also. For instance the function f(x,y) = x^2 + y^2 - 1 has as its 'kernel' the circle x^2 + y^2 = 1.

▲ charcircuit 2 hours ago | parent | prev | next [-]

>but notoriously mathematics runs on javascript

Lean is much more notorious for mathematics.

▲ NooneAtAll3 3 hours ago | parent | prev | next [-]

when '=' is used, it no longer means "set", but "some element of that set" instead

▲ hyperpape 6 hours ago | parent | prev | next [-]

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 6 hours ago \| parent [-]
		"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 ;)

▲ foxes 5 hours ago | parent | prev [-]

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 2 hours ago \| parent [-]
		No. Equality is defined on sets, with exactly one exception, this stupid fucking notation.

▲ josalhor 6 hours ago | parent | prev | next [-]

> 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.

▲

NooneAtAll3 3 hours ago | parent | next [-]

you're confused because it isn't a set

it's a notation for "some element of that set"

▲

FartyMcFarter 6 hours ago | parent | prev [-]

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 4 hours ago \| parent [-]
		f(x) - g(x) ∈ O(1)

▲ dataflow 5 hours ago | parent | prev | next [-]

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".

▲ bo1024 5 hours ago | parent | prev | next [-]

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)).

▲ tokenless 4 hours ago | parent | prev | next [-]

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 2 hours ago \| parent [-]
		Complexity theory studies inherent growth in problems, not bound to a particular machine

▲ edflsafoiewq 5 hours ago | parent | prev [-]

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)).