Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
$\Omega \hspace{.02 in}(\hspace{.06 in}f(n)) \neq 1 \:$, $\:$ since $\: 1\in \Omega \hspace{.02 in}(\hspace{.06 in}f(n)) \:$ would mean there is a positive constant $c$ such that $\;\; c\cdot \hspace{-0.05 in}\left|\hspace{.05 in}f(n)\right| \: \leq \: |1| \;\;$ holds for sufficiently large $n$. $\;\;\;\;\;\;\;$ –  Ricky Demer Jul 30 at 16:24
    
Ok, didn't really think that example through. –  user3236702 Jul 30 at 16:35
1  
Your past tutor is wrong. $O(f(n))=n^3$ is not good notation. Stick to using big-O symbols on the right-hand side of an equality, never the left-hand side (in my experience the latter will lead you astray). Or, just stick to "is an element of", if you're ever in doubt. –  D.W. Jul 30 at 18:00
1  
This looks like it is covered by our reference questions (and things they link to. Did you look at cs.stackexchange.com/q/57/755? It looks like a duplicate to me (i.e., the answers there are enough to answer your question), but if you've read through that material carefully and it is not, I encourage you to edit your question to clarify more specifically what your confusion is, in light of that material. –  D.W. Jul 30 at 18:01
1  
"I've seen the mathematical definitions [of o and ω] and I know that the only difference between them and O and Ω respectively is that rather than "there exists C", it is "for all C"" -- where did you read this? I'd like to see the full version. –  Raphael Jul 30 at 19:35

2 Answers 2

In the case of the $O(f(n))$ and $\Omega(f(n))$ you are correct in that they can be wildly in accurate 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 magnitudes, What $f(n)$ is $\Theta(g(n))$ means is that there are 2 constants, $C_1$ and $C_2$, and 2 values $n_1$,$n_2$ such that $C_1g(n)>f(n)$ for all $n$ greater then $n_1$, and like wise $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 order of magnitudes less then another, When we were in big o notation as long as one constant 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 0 then $f(n)$ is $o(g(n))$, if it is $\infty$ then $f(n)$ is $\omega(g(n))$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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