- **Information & Answers**
(*https://www.mersenneforum.org/forumdisplay.php?f=38*)

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

Landau Notation questionI 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. |

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

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.