2009-09-06, 22:20 | #1 |
Dec 2008
7^{2}×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 (, , 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 |
Dec 2008
7^{2}·17 Posts |
I think that
f(x) >> g(x) translates as: . Although according to Knuth, using an equality in front of a Landau symbol is supposedly abuse of notation (apparently is preferred). Last fiddled with by flouran on 2009-09-06 at 22:49 |
2009-09-06, 23:20 | #3 |
Aug 2006
5,987 Posts |
Good job. It's actually , 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: instead of . |
Thread Tools | |
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 |