Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Functions

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search