mersenneforum.org (https://www.mersenneforum.org/index.php)
-   -   Landau Notation question (https://www.mersenneforum.org/showthread.php?t=12399)

 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 $$\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)}$$
$$f(x)=(\log x)^{1+o(1)}$$.