Skip to main content

From wikipedia, definition of big O notation:

if and only if there is a positive constant M such that for all sufficiently large values of x$x$, f(x)$f(x)$ is at most M multiplied by g(x)$g(x)$ in absolute value. That is, f(x) = O(g(x))$f(x) \in O(g(x))$ if and only if there exists a positive real number M$M$ and a real number x0$x_0$ such that

|f(x)|<= M |g(x)|  for all x> x0. 

$|f(x)|<= M |g(x)| \quad \text{for all} \; x > x_0$

What happens for functions that do not converge (to a constant nor infinity)?

Look at the functions f(x) = |x*sin(x)|$f(x) = |xsin(x)|$, and and g(x) = 10$g(x) = 10$

for each x0$x_0$, there is some x > x0$x > x0$, such that x = k*pi$x = k\pi$, thus f(x) = 0$f(x) = 0$ - so for each M$M$ - M*f(x) > g(x)$Mf(x) > g(x)$ will yield false, and g(x) != O(f(x))$g(x) \; \not\in O(f(x))$

However, it is easy to see that |x*sin(x)|$|xsin(x)|$ is not bounded by any constant as well, thus for each M$M$,x0$x_0$, there is some x > x0$x > x_0$ such that f(x) < M*g(x)$f(x) < Mg(x)$ will also yield false, and f(x) != O(g(x))$f(x) \not\in O(g(x))$

Note: for definition if big O that allows a maximum constant difference between M*f(x)$Mf(x)$ and g(x)$g(x)$, the same idea will apply with g(x) = log(x)$g(x) = \log(x)$

From wikipedia, definition of big O notation:

if and only if there is a positive constant M such that for all sufficiently large values of x, f(x) is at most M multiplied by g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

|f(x)|<= M |g(x)|  for all x> x0. 

What happens for functions that do not converge (to a constant nor infinity)?

Look at the functions f(x) = |x*sin(x)|, and g(x) = 10

for each x0, there is some x > x0, such that x = k*pi, thus f(x) = 0 - so for each M - M*f(x) > g(x) will yield false, and g(x) != O(f(x))

However, it is easy to see that |x*sin(x)| is not bounded by any constant as well, thus for each M,x0, there is some x > x0 f(x) < M*g(x) will also yield false, and f(x) != O(g(x))

Note: for definition if big O that allows a maximum constant difference between M*f(x) and g(x), the same idea will apply with g(x) = log(x)

From wikipedia, definition of big O notation:

if and only if there is a positive constant M such that for all sufficiently large values of $x$, $f(x)$ is at most M multiplied by $g(x)$ in absolute value. That is, $f(x) \in O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that

$|f(x)|<= M |g(x)| \quad \text{for all} \; x > x_0$

What happens for functions that do not converge (to a constant nor infinity)?

Look at the functions $f(x) = |xsin(x)|$, and $g(x) = 10$

for each $x_0$, there is some $x > x0$, such that $x = k\pi$, thus $f(x) = 0$ - so for each $M$ - $Mf(x) > g(x)$ will yield false, and $g(x) \; \not\in O(f(x))$

However, it is easy to see that $|xsin(x)|$ is not bounded by any constant as well, thus for each $M$,$x_0$, there is some $x > x_0$ such that $f(x) < Mg(x)$ will also yield false, and $f(x) \not\in O(g(x))$

Note: for definition if big O that allows a maximum constant difference between $Mf(x)$ and $g(x)$, the same idea will apply with $g(x) = \log(x)$

Post Migrated Here from stackoverflow.com (revisions)
Source Link
amit
  • 313
  • 1
  • 4

From wikipedia, definition of big O notation:

if and only if there is a positive constant M such that for all sufficiently large values of x, f(x) is at most M multiplied by g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

|f(x)|<= M |g(x)|  for all x> x0. 

What happens for functions that do not converge (to a constant nor infinity)?

Look at the functions f(x) = |x*sin(x)|, and g(x) = 10

for each x0, there is some x > x0, such that x = k*pi, thus f(x) = 0 - so for each M - M*f(x) > g(x) will yield false, and g(x) != O(f(x))

However, it is easy to see that |x*sin(x)| is not bounded by any constant as well, thus for each M,x0, there is some x > x0 f(x) < M*g(x) will also yield false, and f(x) != O(g(x))

Note: for definition if big O that allows a maximum constant difference between M*f(x) and g(x), the same idea will apply with g(x) = log(x)