[Solved]: Big-O and little-o notation

Problem Detail: 

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.

Asked By : user3280193

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53815

3.2K people like this

 Download Related Notes/Documents