O and o Functions
Date: 01/08/99 at 06:06:24 From: Michael Kuhn Subject: Twin-Prime Theorem I'm a German high school student doing research on primes and twin primes. One part of my research is the proof of a theorem that shows you how many twin primes exist below n. I found the theorem at Eric Weisstein's CRC Concise Encyclopedia of Mathematics: http://mathworld.wolfram.com/TwinPrimes.html Unfortunately, this site is not always available, so I'm going to do my best to describe what Weisstein is saying. Let pi_2(x) be the number of twin primes p and p+2 that are less than x. (Note the "_" means "subscript.") It's been shown that x ln ln x pi_2(x) <= c * pi_2 -------- [ 1 + O(-------) ] (ln x)^2 ln x where pi_2 is the twin primes constant, and c is another constant. The O is the capital letter O and is some kind of a function. My problem is, I couldn't find out what this big O notation means. Can you please explain it to me? Thank you very much! Yours sincerely, Michael Kuhn
Date: 01/08/99 at 09:47:07 From: Doctor Rob Subject: Re: Twin-Prime Theorem Thanks for writing to Ask Dr. Math! f(n) = O(g(n)) means that there exists some C independent of n and some N > 0 such that |f(n)| <= C*g(n) for all n > N. Another way of saying this is that: lim sup |f(n)|/g(n) < infinity n It means that the rate of growth of f(n) is no more than a constant times the rate of growth of g(n). Example: 5*n^3 + 17*n + 1000 = O(n^3), with C = 6 and N = 10. You may also encounter o(f(n)). f(n) = o(g(n)) means that: lim f(n)/g(n) = 0. n->infinity Example: 987*ln(n) = o(n). It means that the rate of growth of f(n) is strictly less than any constant times the rate of growth of g(n). Notice that there is an important difference between O and o in this context! There is a clearer way to express the pi_2(x) function, as a constant times an integral: pi_2(x) =~ 1.320323632 int[dx/(ln x)^2] from 2 to x (Note that =~ means "approximately equal to.") You can find more information on this version at Chris Caldwell's page: http://www.utm.edu/research/primes/lists/top20/twin.html - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.