0
$\begingroup$
  • $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)$?

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Yuval Filmus
    Feb 21 '18 at 15:40
  • 2
    $\begingroup$ 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$ ...). $\endgroup$
    – md5
    Feb 21 '18 at 15:41
  • $\begingroup$ @Yuval Filmus If $\Omega(n) = \{n, n^{2}, n^{1000000}, 2^{n}, ...\}$ would be a correct (sloppy) equality, what would be $O(n) = ...$? $\endgroup$
    – A.L. Verminburger
    Feb 21 '18 at 15:54
  • 1
    $\begingroup$ You cite three (really, two) sources but none of them contains the (false) statements you (dis)credit to them. $\endgroup$
    – David Richerby
    Feb 21 '18 at 16:04
  • 2
    $\begingroup$ @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)$? $\endgroup$
    – David Richerby
    Feb 21 '18 at 22:06
3
$\begingroup$

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

So, there is no contradiction. But you do need to look at your definitions a bit more carefully.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – A.L. Verminburger
    Feb 21 '18 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.