mersenneforum.org Landau Notation question
 Register FAQ Search Today's Posts Mark Forums Read

 2009-09-06, 22:20 #1 flouran     Dec 2008 72×17 Posts Landau Notation question I have a rather simple question which requires a direct answer: We have two functions, f(x) and g(x). I know that f(x) << g(x) is the same as f(x) = O(g(x)). But if f(x) >> g(x), how can I write f(x) in terms of g(x) using the one of the four Landau symbols ($\Omega$, $\omega$, o, or O)? I suspect that f(x) >> g(x) means the same as f(x) = o(g(x)), but I am not sure. Last fiddled with by flouran on 2009-09-06 at 22:20
 2009-09-06, 22:48 #2 flouran     Dec 2008 72·17 Posts I think that f(x) >> g(x) translates as: $f(x) = \omega(g(x))$. Although according to Knuth, using an equality in front of a Landau symbol is supposedly abuse of notation (apparently $\in$ is preferred). Last fiddled with by flouran on 2009-09-06 at 22:49
 2009-09-06, 23:20 #3 CRGreathouse     Aug 2006 5,987 Posts Good job. It's actually $\Omega(g(x))$, but now you're in the right neighborhood. f(x) = o(g(x)) is almost upside-down. Certainly the equals sign is an abuse of notation -- otherwise O(n) = O(n^2) would imply O(n^2) = O(n) which is of course false. For more complicated expressions (those not of the form f(x) = symbol(g(x)) for symbol in o, O, Omega, omega, Theta, soft-O, etc.) you also need to use quantifiers: $\exists g(x)\in o(1):f(x)=(\log x)^{1+g(x)}$ instead of $f(x)=(\log x)^{1+o(1)}$.

 Similar Threads Thread Thread Starter Forum Replies Last Post Don Miscellaneous Math 1 2016-09-23 16:55 spyros Information & Answers 19 2009-06-19 20:28 mgb Lounge 5 2007-06-16 20:54 meknowsnothing Math 1 2007-05-31 03:32 eepiccolo Math 7 2005-06-04 23:01

All times are UTC. The time now is 21:07.

Wed Oct 5 21:07:30 UTC 2022 up 48 days, 18:36, 1 user, load averages: 1.47, 1.32, 1.26