# Is there a contradiction between "set-theoretic" and "formal" definition of "Big-O"?

• $O(n) = \{n, n^{2}, n^{1000000}, 2^{n}, ...\}$ [Source A], [Source B]
• Say $t_{n} \in O(n)$
• By formal definition $t_{n} \leq k \cdot n$ [Source C]

But how can this be? Say $t_{n}$ is actually $n^{2}$, then $t_{n} \leq k \cdot n$ is just false. Would it not be more logical to have $t_{n} \geq k \cdot n$ as a formal definition acompanying $O(n)$?

• Your first "definition" isn't really a definition - you're not explaining which functions appear on the right-hand side. It also doesn't appear in any of your sources. The first source mentions that a function which is $O(n)$ is also $O(n^2)$, i.e., $O(n) \subseteq O(n^2)$. The function you list on the right-hand side actually all belong to $\Omega(n)$. Feb 21 '18 at 15:40
• I don't see what in your sources A and B makes you think that we could write $O(n)=\{n,n^2,\ldots\}$. In general your last definition is the right one (with appropriate quantifiers, namely there exists $k,n_0$ s.t. for all $n>n_0$ ...).
– md5
Feb 21 '18 at 15:41
• @Yuval Filmus If $\Omega(n) = \{n, n^{2}, n^{1000000}, 2^{n}, ...\}$ would be a correct (sloppy) equality, what would be $O(n) = ...$? Feb 21 '18 at 15:54
• You cite three (really, two) sources but none of them contains the (false) statements you (dis)credit to them. Feb 21 '18 at 16:04
• @A.L.Verminburger That's not a definition. It's just a collection of examples. For example, can you tell me whether $e^{\sqrt{\log n}}\in O(n)$ based on the three examples $1$, $0.5n$ and $n$? Heck, could you even tell from those examples whether $2n\in O(n)$? Feb 21 '18 at 22:06

The first statement you made is not correct. $O(n)$ is the set of all functions $f(n)$ that are bounded above by some constant multiple of $n$ for sufficiently large $n$. The functions you have listed all belong to the set $\Omega(n)$ which is almost like $O(n)$ but instead of being bounded above by $k\cdot n$, this is the set of functions that are bounded below by $k\cdot n$ for sufficiently large $n$.
• I misinterpreted the statement "when we say an algorithm is of O(n), it's also O(n^2), O(n1000000), O(2^n)" in source A to mean what I wrote in first bullet point. So indeed C is correct and concrete examples would be $O(n)=\{...,1,...k_{1} \cdot n\}$ and $\Omega(n) = \{k_{2} \cdot n , ...., n^{2}, ....\}$ such that the codomain of all functions in sets are always positive. And as a side note $\Theta(n)=\{k_{1} \cdot n, ..., k_{2} \cdot n\} : k_{1}, k_{2} > 0$. Feb 21 '18 at 16:30