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)=2n+1/n
and g(x)=2n
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(x0 and L(x)® 1 as x®¥. If g is non-zero, this is the same as saying f(x)/g(x)® 1 as x®¥.

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

  1. f(x) ~ f(x) for all functions f
  2. f(x) ~ g(x)Û g(x) ~ f(x)
  3. f(x) ~ g(x), g(x) ~ h(x)Þ 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)=W(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