Landau Notation question

flouran · 2009-09-06, 22:20

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.

flouran · 2009-09-06, 22:48

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

CRGreathouse · 2009-09-06, 23:20

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

2009-09-06, 22:20	#1
flouran Dec 2008 7²·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 7²×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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New Solutions (Landau's Problems - Number Theory)	Don	Miscellaneous Math	1	2016-09-23 16:55
prime 95 notation	spyros	Information & Answers	19	2009-06-19 20:28
???Math. notation???	mgb	Lounge	5	2007-06-16 20:54
Congruence notation	meknowsnothing	Math	1	2007-05-31 03:32
Twin prime conjecture work, notation question	eepiccolo	Math	7	2005-06-04 23:01

2009-09-06, 23:20	#3
CRGreathouse Aug 2006 13543₈ 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)}$ .