mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2009-09-06, 22:20   #1
flouran
 
flouran's Avatar
 
Dec 2008

72×17 Posts
Default 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
flouran is offline   Reply With Quote
Old 2009-09-06, 22:48   #2
flouran
 
flouran's Avatar
 
Dec 2008

72·17 Posts
Default

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
flouran is offline   Reply With Quote
Old 2009-09-06, 23:20   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

5,987 Posts
Default

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)}.
CRGreathouse is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 21:07.


Wed Oct 5 21:07:30 UTC 2022 up 48 days, 18:36, 1 user, load averages: 1.47, 1.32, 1.26

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔