-   Information & Answers (
-   -   Landau Notation question (

flouran 2009-09-06 22:20

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 ([TEX]\Omega[/TEX], [TEX]\omega[/TEX], 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:
[TEX]f(x) = \omega(g(x))[/TEX].
Although according to Knuth, using an equality in front of a Landau symbol is supposedly abuse of notation (apparently [TEX]\in[/TEX] is preferred).

CRGreathouse 2009-09-06 23:20

Good job. It's actually [tex]\Omega(g(x))[/tex], 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:
[tex]\exists g(x)\in o(1):f(x)=(\log x)^{1+g(x)}[/tex]
instead of
[tex]f(x)=(\log x)^{1+o(1)}[/tex].

All times are UTC. The time now is 03:46.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.