Asymptotic and the big O

By Yatir Halevi on Friday, January 25, 2002 - 12:09 pm:

I don't know if I understand when do you say that one function is asymptotic to another, and what is the big-oh O() term mean?

if f(x)=2^n+1/n
and g(x)=2ⁿ
Does it mean that f(x) is asymptotic to g(x), and that f(x)=O(g(x))

Thanks,
Yatir

By Michael Doré on Friday, January 25, 2002 - 05:28 pm:

f (x)

is asymptotic to

g (x)

means that there exists a function

L (x)

such that

f (x) = g (x) L (x 0

and

L (x) \to 1

x \to \infty

. If

g

is non-zero, this is the same as saying

f (x) / g (x) \to 1

x \to \infty

The statement '' $f$ is asymptotic to $g$ '' is written $f (x) ~ g (x)$ . You are correct that with your example $2^{n + 1 / n} ~ 2^{n}$ because $2^{n + 1 / n} / 2^{n} = 2^{1 / n} \to 1$ as $n \to \infty$ . You might like to check that $~$ is an equivalence relation - in other words:

$f (x) ~ f (x)$ for all functions $f$
$f (x) ~ g (x) \Leftrightarrow g (x) ~ f (x)$
$f (x) ~ g (x)$ , $g (x) ~ h (x) \Rightarrow f (x) ~ h (x)$

f (x) = O (g (x))

is a weaker condition than

f (x)

. It just means that there exist constants

A

B

such that for all

x > B

we have

| f (x) | < A | g (x) |

. In other words

| f (x) / g (x) |

is bounded for sufficiently high

x

. If

f

g

are asymptotic then

f (x) = O (g (x))

but the converse isn't necessarily true.

There is also a symbol for an asymptotic lower bound. $f (x) = Ω (g (x))$ means that there exist constants $A$ , $B$ such that $A > 0$ and for all $x > B$ we have $| f (x) | > A | g (x) |$ . @ @

By Yatir Halevi on Friday, January 25, 2002 - 05:58 pm:

Thanks.

Yatir