1
$\begingroup$

I think I have a passable understanding of what Big-O and little-o mean. I'm just wondering whether it makes sense notation-wise to state something like the following:

$$O(n^c) = o(n^k) \text{ for } k > c$$

For example, $O(n^2) = o(n^3)$ since $3 > 2$. Basically, any constant times $n^2$ will still grow more slowly than any constant times $n^3$ for large enough $n$.

Does it make sense to have both sides of an equation consist of big-O and/or little-o notations like this, or does one side of the equation have to consist of a bare function only? Thanks.

$\endgroup$
2
$\begingroup$

I can suggest two different plausible ways of interpreting the notation.

  • One way to understand notation like $O(n^2)$ is to treat it as denoting a set of functions. With this viewpoint, we might interpret the claim $O(n^2) = o(n^3)$ as claiming that the set $O(n^2)$ contains exactly the same set of functions (no more, no fewer) as the set $o(n^3)$.

  • Another way to understand notation like $n \lg n = O(n^2)$ is to treat this as claiming that the function $n \lg n$ is in the set $O(n^2)$. In other words, when we have $= O(n^2)$ on the right-hand side, we treat that as a sloppy short-hand for $\in O(n^2)$. With this viewpoint, we might interpret the claim $O(n^2) = o(n^3)$ as being equivalent to $O(n^2) \subseteq o(n^3)$, i.e., that the set $O(n^2)$ is a subset of the set $o(n^3)$.

Both interpretations are plausibly defensible: neither one is ridiculous or obviously wrong.

Notice how we start from two different perspectives that are very similar, yet we end up with two completely different interpretations of the claim $O(n^2) = o(n^3)$. This is a sign that writing something like $O(n^2) = o(n^3)$ is a bad idea -- it can easily be misinterpreted. It would be better if the author wrote this differently, in a way that makes it clearer what the author's intent was.

So, this notation is ambiguous or potentially confusing. If you see this in some written material and can't ask the author, you'll just have to guess what was meant from context.

$\endgroup$
2
$\begingroup$

Many people cringe at the notation $n^2=O(n^3)$, since, strictly speaking, $O(n^3)$ is a set of functions, defined by $$ O(n^3)=\{f\mid \exists k>0, N\ge 0\, [f(n)\le kn^3\text{ for all }n\ge N\} $$ In other words, $$ O(n^3)=\{1, n, n^2, n^2\log n, n^3, 3n^3+15n^2,\dotsc\} $$ which is to say $O(n^3)$ consists of all functions $f(n)$ that are eventually less than a constant multiple of $n^3$.

With this understanding, to be precise we should write $n^2\in O(n^3)$, rather than the sloppier $n^2=O(n^3)$. This means that it is indeed notationally correct to ask whether $O(n^2)=o(n^3)$, since they are both sets of functions.

[Note, by the way, I'm not asserting that $O(n^2)=o(n^3)$. I'll leave that to you to prove or disprove.]

$\endgroup$
  • $\begingroup$ Thanks, would it make better sense to say, then, something like: O(n^2) ⊆ o(n^3)? To indicate that if a function is in the set O(n^2), then that function must also be in the set o(n^3)? $\endgroup$ – user3280193 Feb 29 '16 at 22:33

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.