To describe lower bounds we use the big-omega notation f(n)=Ω(g(n)) usually defined by saying for some constant c>0 and all large enough n, f(n)≥c g(n). This has a nice symmetry property, f(n)=O(g(n)) iff g(n)=Ω(f(n)). Unfortunately it does not correspond to how we actually prove lower bounds.
For example consider the following algorithm to solve perfect matching: If the number of vertices is odd then output "No Perfect Matching" otherwise try all possible matchings.
We would like to say the algorithm requires exponential time but in fact you cannot prove a Ω(n2) lower bound using the usual definition of Ω since the algorithm runs in linear time for n odd. We should instead define f(n)=Ω(g(n)) by saying for some constant c>0, f(n)≥ c g(n) for infinitely many n. This gives a nice correspondence between upper and lower bounds: f(n)=Ω(g(n)) iff f(n) is not o(g(n)).
On a related note some researchers like to say f(n)∈O(g(n)) viewing O(g(n)) as a set of functions. This trades off a nice clear unambiguous notation with something ugly for the sake of formality. Yuck.
How is f(n) = O(g(n)) nice clear unambiguous?
ReplyDeleteIf f(n) = O(g(n)) and h(n) = O(g(n)), do we have f(n) = h(n)?
(No.)
I use the "f(n)=O(g(n))" notation myself, but I must admit that the "f(n) \in O(g(n))" option has merit. First, it is useful to think of this as a set of functions when doing "O arithmetic", as in "(1+o(1))g(n)" or "n^{(O(1))}". Also, it would help the lower bound issues by writing "f(n) \not\in O(g(n))", and saving the Omega notation for the few cases where we need it as it is now.
ReplyDeleteOn the other hand most of us are already used to "f(n)=O(g(n))", and it is not as if as we are anywhere near the level of notational abuse of, say, Quantum Field Theory...
- Eldar.
I like the set definition myself, but in writing I might say "T(n) is O(n)" where the "is" is substituting a "=". (Equality is two directional, while "is" is one directional, depending on what the definition of "is" is.)
ReplyDeleteI'm confused by the litte-oh defintion: isn't f(n)<c*g(n) what it means? (I.e., the same as the big-O defintion, but with a < instead of a >=, and c is always positive?)
Usually "f(n)=o(g(n))" means that f(n)/g(n)-->0, or alternatively that for every c>0, |f(n)|<c|g(n)| for n large enough.
ReplyDelete- Eldar.
I don't understand the statement: "f(n)=?(g(n)) iff g(n) is not o(f(n))"
ReplyDeleteConsider the case where g(n) represents constant time, and f(n) is say exponential time. Clearly g(n) is a lower bound for f(n), so the condition f(n)=?(g(n)) holds. Also clearly, f(n) is a loose upper bounds for g(n), so g(n) is o(f(n)), contradicting the statement above.
I'll try again. (Whatever happened to Unicode?)
ReplyDeleteI don't understand the statement: "f(n)=Omega(g(n)) iff g(n) is not o(f(n))"
Consider the case where g(n) represents constant time, and f(n) is say exponential time. Clearly g(n) is a lower bound for f(n), so the condition f(n)=Omega(g(n)) holds. Also clearly, f(n) is a loose upper bounds for g(n), so g(n) is o(f(n)), contradicting the statement above.
I got that backwards. Should have been "f(n) is Ω(g(n)) iff f(n) is not o(g(n))". I'll fix it in the post.
ReplyDeleteThanks, makes perfect sense now. -Jon
ReplyDeleteCount one more vote for the "?" crowd. :-) Of course, in keeping with tradition I do use "= O(g(n))" in writing, but I wish everyone would move to the more technically correct "?". The first anonymous commenter has already pointed out my main problem with "=".
ReplyDelete-- Amit Chakrabarti
Hmm, when I posted the above, I thought I was typing a "belongs to" character (LaTeX $\in$), but it has appeared as "?" on this Firefox window on this Mac.
ReplyDelete-AmitC
Use ∈ for ∈ and Ω for Ω. You can see a list of special characters here.
ReplyDeletef(n) is O(g(n)) reads better than writing out set membership and is more accurate than using =.
ReplyDeleteGiven this notation there is not need to define the weak Ω at all: Why not simply say that f(n) is not o(g(n)) instead?
The real temptation to use ∈ instead of 'is' comes when doing extensive arithmetic with O(g(n)) quantities.
It is awkward to keep connecting lines with 'which is'
instead of set equality.
It is nature that Everybody get confusion with the representation f(n)=O(g(n)). One point I want to clearify is that the above mentioned representation is an assertion. Some author uses this represention(abuse of notation) keeping internally the meaning " f(n) is O(g(n)) or f(n) belongs to O(g(n))".
ReplyDeletewould logn! be big omega of nlogn?
ReplyDeleteIf f(x)<=c1O(a(x)) and g(x)<=c2O(b(x))
ReplyDeletefrom comment 1 above
we know that
f(x)*g(x) <= maxof(c1orc2) O(a(x)) * O(b(x))
If f(x)<=c1O(a(x)) and g(x)<=c2O(b(x))
ReplyDeletefrom comment 1 above
we know that
f(x)*g(x) <= maxof(c1orc2) O(a(x)) * O(b(x))
I have learn discrete math at Univ,
ReplyDeleteso please show me
how do I choose k for prove Big-O notation ?
what's principle?
I have learn discrete math at Univ,
ReplyDeleteso please show me
how do I choose k for prove Big-O notation ?
what's principle?
I have learn discrete math at Univ,
ReplyDeleteso please show me
how do I choose k for prove Big-O notation ?
what's principle?
Is there any positive function f(n) which is neither O(n) nor big-omega(n)??
ReplyDeleten0pe
Deleten0pe
Deletesara khan
nooooooooooooooooooooooooooooooooooooooooooooooooooo
ReplyDeletein which case omega is required?
ReplyDeleteYes, Θ(n) which lie between O(n) and big-omega(n),
ReplyDeletehttp://ip-techmania.blogspot.in/2012/06/analysing-big-oh-notation.html