# Asymptotic Relationship from Limit

F(n) = n-100 G(n) = n-200

I am trying to show the asymptotic relationship between these two functions using limits.

I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c.

From the Big O theorem,

From the Big Omege theorem,

My question is: How I supposed to determine whether they are f = O(g(n)) or f = Ω(g(n))

In general, what is a good way to find the relationship between given two functions?

• Your theorems are wrong. I suggest ignoring them. – Yuval Filmus Sep 1 '19 at 15:45
• What theorem is wrong? The one in pictures? They are from following books: Algorithms 2006 S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani – Emrah Sariboz Sep 1 '19 at 15:46
• The two theorems you quote are unfortunately wrong. – Yuval Filmus Sep 1 '19 at 15:48
• Could you please answer why they are wrong? Or what is a good way to find the relationship between given two functions? – Emrah Sariboz Sep 1 '19 at 15:49
• There is a counterexample in my answer. – Yuval Filmus Sep 1 '19 at 16:00

The theorems you quote are unfortunately wrong. As an example, $$2 + \sin n = \Theta(1)$$ although the limit $$\lim_{n\to\infty} \frac{2+\sin n}{1}$$ doesn't exist.

Here are some theorems which do hold.

Theorem 1. Let $$f,g$$ be two functions such that $$f(n),g(n)$$ are eventually positive. If the limit $$c := \lim_{n\to\infty} f(n)/g(n)$$ exists then

1. $$f(n) = O(g(n))$$ iff $$0 \leq c < \infty$$.
2. $$f(n) = \Omega(g(n))$$ iff $$0 < c \leq \infty$$.
3. $$f(n) = \Theta(g(n))$$ iff $$0 < c < \infty$$.
4. $$f(n) = o(g(n))$$ iff $$c = 0$$.
5. $$f(n) = \omega(g(n))$$ iff $$c = \infty$$.

Theorem 2. If $$f,g$$ are two polynomials which are eventually positive, then the limit $$\lim_{n\to\infty} f(n)/g(n)$$ exists.

Theorem 3. Let $$f,g$$ be two functions such that $$f(n),g(n)$$ are eventually positive. Then

1. $$f(n) = O(g(n))$$ iff $$\lim\sup_{n\to\infty} \frac{f(n)}{g(n)} < \infty$$.
2. $$f(n) = \Omega(g(n))$$ iff $$\lim\inf_{n\to\infty} \frac{f(n)}{g(n)} > 0$$.
3. $$f(n) = o(g(n))$$ iff $$\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$$.
4. $$f(n) = \omega(g(n))$$ iff $$\lim_{n\to\infty} \frac{f(n)}{g(n)} = \infty$$.
• So, according to your theorem, the answer of my question where f(n) is n-100, g(n) is n-200, is f(n)=Ω(g(n)). However, the answer is f(n) = O(g(n)) because both function is O(n). – Emrah Sariboz Sep 1 '19 at 16:19
• Both are correct. – Yuval Filmus Sep 1 '19 at 16:27
• Can we also assume it is (n)=Θ(g(n)) ? – Emrah Sariboz Sep 1 '19 at 16:31
• This is also correct. In fact, $f = \Theta(g)$ iff $f = O(g)$ and $f = \Omega(g)$. – Yuval Filmus Sep 1 '19 at 16:45
• It's clear now. Thank you! – Emrah Sariboz Sep 1 '19 at 16:46