Can someone clarify landau symbols definition please?

Question

I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know that technically the correct notation is to say $f(n)$ is an element of $O(f(n))$, not $f(n) = O(f(n))$.

Loosely, my understanding is this, given$ f(n) = n^2 + 2n +log(n)$ Big O represents the upper magnitude, so it would be correct (according to a past CS tutor), but not very accurate, to say $O(f(n)) = n^3$, but incorrect to say $O(n) = log(n)$, whereas the $Ω(f(n)) $represents the lower bound, so it would be correct, but inaccurate to say $Ω(f(n)) = log(n)$ or (not sure about this one), $Ω(f(n)) = 1$.

I know that $Θ(f(n))$ is defined as the intersection of $O(f(n))$ and $Ω(f(n))$, but is it valid to drop off lower orders of magnitude in the case of $Θ(f(n))$? ie. is $Θ(f(n)) = n^2$ correct? If not, what is the correct equality?

What I am entirely unsure about is $o(f(n))$ and $ω(f(n))$. I've seen the mathematical definitions and I know that the only difference between them and $O(f(n))$ and $Ω(f(n)) $respectively is that rather than "there exists C", it is "for all C", but my understanding of mathematical symbols is (at this stage) embarrassing. If anyone could shed some light on all of the above it'd be appreciated, thanks.

Answer 1

You cannot write $O(f(n)) = n^3$ or $O(f(n)) = \log n$ since this is a "syntax error". Big O notation is not symmetric, and can only be used on the right-hand side, or in a chain of inequalities $f(n) = O(g(n)) = O(h(n))$ (formally, this means $f(n) \in O(g(n)) \subseteq O(h(n))$).

Your function $f(n)$ satisfies $f(n) = \Theta(n^2)$, as well as $f(n) = \Theta(n^2 + 2n + \log n)$, $f(n) = \Theta(n^2 + n)$, $f(n) = \Theta(17n^2 + n/\log n + 5\log\log n)$, and many more. Regarding big O and big Omega, there are even more options, for example $f(n) = O(n!^2)$ and $f(n) = \Omega(1/n)$.

That said, when stating big Theta estimates, we are usually aiming for the simplest possible expression on the right, so in your case we are most satisfied with $f(n) = \Theta(n^2)$. With big O and big Omega, we are looking for both simplicity and tightness, which is why we would be most satisfied with $f(n) = O(n^2)$ and $f(n) = \Omega(n^2)$ ($f(n) = \Omega(\log n)$, for example, is simple but not tight).

---

The notation $f(n) = \Theta(g(n))$ means that for some constants $c,C>0$, $$ c \leq \frac{f(n)}{g(n)} \leq C. $$ In other words, $f(n),g(n)$ are the same up to a (multiplicative) constant. The notation $f(n) = O(g(n))$ corresponds to just the upper bound $f(n) \leq Cg(n)$, and $f(n) = \Omega(g(n))$ corresponds to just the lower bound $f(n) \geq cg(n)$.

If you think of $f(n) = \Theta(g(n))$ as $f(n) = g(n)$ (up to constants), then $f(n) = O(g(n))$ is like $f(n) \leq g(n)$, and $f(n) = \Omega(g(n))$ is like $f(n) \geq g(n)$.

The notation $f(n) = o(g(n))$ just means that $f(n)/g(n) \to 0$, and $f(n) = \omega(g(n))$ just means that $f(n)/g(n) \to \infty$, so that $f(n) = o(g(n))$ is the same as $g(n) = \omega(f(n))$.

(Caveat: the discussion above assumes all functions are positive.)

Answer 2

In the case of $O(f(n))$ and $\Omega(f(n))$ you are correct in that they can be wildly inaccurate and still be correct, for instance, $n$ is $O(2^n)$ - this just does not provide good information.

For $\Theta$ yes you can drop the lower orders of magnitude. What "$f(n)$ is $\Theta(g(n))$" means is that there are two constants, $C_1$ and $C_2$, and two values $n_1$, $n_2$ such that $C_1g(n)>f(n)$ for all $n$ greater then $n_1$, and likewise $C_2g(n)Nf(n)$ for all $n$ greater then $n_2$. In your case we can see that multiplying $n^2$ even by 2 will dwarf the remaining values of $f(n)$ for sufficiently large $n$, likewise multiplying by 1 will make it always smaller.

Little $o$ and $\omega$ notation is used to describe a function as being orders of magnitude less then another. When we were in big $o$ notation, as long as one constant $C$ existed such that $Cg(n)>f(n)$ then $f(n)$ is $O(g(n))$, with little $o$, every possible $c$ must cause this to happen. The easiest way to find this is to take the limit of $\lim_{x \to \infty} \frac{f(n)}{g(n)}$: if it is zero then $f(n)$ is $o(g(n))$; if it is $\infty$ then $f(n)$ is $\omega(g(n))$

Answer 3

With $\mathcal{O}$ you always want to have a function that is more or equal to your function asymptotically. So you can pretty much calculate with it.

Have in mind we are using $n \in \mathbb{N} = \{1, 2, 3,...\}$. That's relevant for the first inequality.

$f(n) = n^2+2n+5 \leq n^2+2n^2+5 = 3n^2+5 \stackrel{n \geq 3}{\leq} 3n^2+n^2 = 4n^2$

You can then use that $4$ as the constant factor $c$ so you'll get: $f(n) \in \mathcal{O}(n^2)$

And that is pretty accurate. You can however still size up the $4n^2$ and still be valid. The more margin you introduce, the more accuracy you lose.

---

The idea behind dropping off lower orders of magnitude for $\Theta$ is similar.

By now we know $f(n) \in \mathcal{O}(n^2)$ with $c=4$

For $\Omega$ you just drop of summands, so it gets smaller. $f(n) = n^2+2n+5 \geq n^2 + 5 \geq n^2 \implies f(n) \in \Omega(n^2)$

Now you now $f(n) \in \mathcal{O}(n^2)$ and $f(n) \in \Omega(n^2)$

This directly implies $f(n) \in \Theta(n^2)$