2
$\begingroup$

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,

enter image description here

From the Big Omege theorem,

enter image description here

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?

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

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$.
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Emrah Sariboz Sep 1 at 16:19
  • 1
    $\begingroup$ Both are correct. $\endgroup$ – Yuval Filmus Sep 1 at 16:27
  • $\begingroup$ Can we also assume it is (n)=Θ(g(n)) ? $\endgroup$ – Emrah Sariboz Sep 1 at 16:31
  • 1
    $\begingroup$ This is also correct. In fact, $f = \Theta(g)$ iff $f = O(g)$ and $f = \Omega(g)$. $\endgroup$ – Yuval Filmus Sep 1 at 16:45
  • $\begingroup$ It's clear now. Thank you! $\endgroup$ – Emrah Sariboz Sep 1 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.