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$
6
  • $\begingroup$ Your theorems are wrong. I suggest ignoring them. $\endgroup$ Sep 1, 2019 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$ Sep 1, 2019 at 15:46
  • 1
    $\begingroup$ The two theorems you quote are unfortunately wrong. $\endgroup$ Sep 1, 2019 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$ Sep 1, 2019 at 15:49
  • $\begingroup$ There is a counterexample in my answer. $\endgroup$ Sep 1, 2019 at 16:00

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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