Proving the asymptotic relationship of functions using infinite limits

755 Views Asked by At

Is it a valid to say that given two continuous real functions $f$ and $g$ that $f \in \Theta(g)$ if: $$\lim_{n \to \infty}{\frac{f(n)}{g(n)}} = c\text{, where c is some constant }0<c<\infty$$

Similarly for $\Omega$ and $\mathcal{O}$: $$f \in \mathcal{O}(g) \implies \lim_{n \to \infty}{\frac{f(n)}{g(n)}} = 0$$ $$f \in \Omega(g) \implies \lim_{n \to \infty}{\frac{g(n)}{f(n)}} = 0$$

Please let me know how I'm wrong if these intuitions are incorrect.

1

There are 1 best solutions below

3
On BEST ANSWER

$$ f \in \Theta(2f)$$

$$f \in \mathcal{O}(f)$$

$$f \in \Omega(f)$$

Edit: elaborating on my answer. When using these notations the functions being dealt with are almost always positive valued for the contexts I've seen them used in; if they're not always positive you can adjust the definitions with absolute values.

Big-$\mathcal O$: $f \in \mathcal{O}(g)$ means that for sufficiently large $n$,

$$ f(n) \le k \cdot g(n) \text{ for some constant $k$ > 0}$$

If $g$ is non-zero for $n$ large enough, you can say that this means:

$$ \lim_{n \to \infty} \frac {f(n)}{g(n)} < \infty$$

If the above holds for any $k>0$, no matter how small in magnitude, as long as you make $n$ large enough, then:

$$f \in o(g)$$

If $g$ is non-zero for $n$ large enough, you can say that this means:

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$

For $\Omega$, $\omega$ we say that:

$$f \in \mathcal{O}(g) \iff g \in \Omega(f)$$

$$f \in o(g) \iff g \in \omega(f)$$

If for $n$ sufficiently large, there exists positive constants $k_1, k_2$ such that:

$$k_1 \cdot g(x) \le f(x) \le k_2 \cdot g(x)$$

then we say that $f \in \Theta(g)$. Another way to look at it is that:

$$f \in \Theta(g) \iff \left({f \in \mathcal{O}(g) \land f \in \Omega(g)}\right)$$ There's another notation that means that for $n$ sufficiently large, $f$ and $g$ act almost the same:

$$f \sim g \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$$

Comment: If $f(x)$ is a real function, then instead of $x \to \infty$, you might want to consider a constant $a$ where $\vert x - a \vert < \epsilon$, with $\epsilon > 0$ sufficiently small, in which case you might want to put $(x \to a)$ on the side of the equation for clarity, or write something like $f \underset{a}{\sim} g$.