2
$\begingroup$

I am trying to prove the following statement.

if $\displaystyle \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}= \infty$, then $f(n) = \Omega(g(n))$ but $f(n) \neq O(g(n))$


What I've done so far


Using the definition of limit: $\forall M>0 \quad \exists n_0 : \forall n \ge n_0 \quad \displaystyle\frac{f(n)}{g(n)} > M$
So I multiplied both halves by $g(n)$ obtaining $f(n) > M\cdot g(n)$
I therefore chose a value $c_1$ that respect the condition $0 \le M \le c_1$ in order to define the relation $0 \le c_1g(n)\le f(n)$ that proves that $f(n) = \Omega(g(n))$


So now my questions are:

  • Is the (first part of the) solution mathematically right?
  • How can I mathematically prove that $f(n) \neq O(g(n))$?

I'm struggling a bit to prove the second part of the demonstration.
The main idea I had is to do a reductio ad absurdum where I state that the value $c_2$ I get (following the definition of $O(g(n))$) leads me to a contradiction. But I'm not entirely sure it makes sense.

Thank you in advance for your time.

$\endgroup$
1
$\begingroup$

Your basic idea is good. Here is how you would approach it:

Let us assume towards contradiction that $\exists c_2,n_0:\forall n>n_0:f(n)\le c_2\cdot g(n)$

In particular, we can re-write this as:

$$\exists c_2,n_0:\forall n>n_0:\frac{f(n)}{g(n)}\le c_2$$

Now, since $\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}=\infty$, then we know by definition of the limit that $$\forall M>0:\exists n_0:\forall n>n_0:\frac{f(n)}{g(n)}>M$$

In particular, for any $c_2$ and $n_0$, there is some $n>n_0$ with $f(n)>c_2\cdot g(n)$. Hence, we get a contradiction to the assumption.

$\endgroup$
4
  • $\begingroup$ I wrote almost the same proof as you wrote above. I wasn't sure if that made sense, but now know for sure! Thank you very much! $\endgroup$ Jul 22 at 19:48
  • $\begingroup$ @LukeTheWolf this proof is directly following the definition of big-O and the limit definition that you see in calculus classes. It is very formal, but not always as understandable :o $\endgroup$
    – nir shahar
    Jul 22 at 20:00
  • $\begingroup$ Unfortunately, I know it is very formal, but I was asked to make a formal demonstration. Perhaps can you give me a few more tips on how to make that demonstration easier, but just as effective? $\endgroup$ Jul 22 at 20:04
  • 1
    $\begingroup$ @LukeTheWolf sadly, I do not know of another way, except for using the big-O definition using limits. In that definition, $f$ is said to be $O(g)$ if $\limsup_{n\rightarrow \infty} \frac{f(n)}{g(n)}<\infty$ and as you can see, it is exactly what you asked in the question (and hence not an interesting solution since it just assumes the answer) $\endgroup$
    – nir shahar
    Jul 22 at 20:27
1
$\begingroup$

Suppose $f(n)=n^4,g(n)=n$, so

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\frac{n^4}{n^3}=\frac{n^3}{1}=\infty.$$

That means $f(n)=\Omega(g(n))$ and $f(n)\neq\mathcal{O}(g(n)).$ As a result, if $f(n)=\omega(g(n))$, then we can conclude that, $f(n)=\Omega(g(n))$ and $f(n)\neq \mathcal{O}(g(n)).$

Note that in a such case that

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty$$ easily we can conclude that $f(n)=\omega(g(n))$.

$\endgroup$
3
  • $\begingroup$ Thanks for the reply, but I would like to find the mathematical proof that determines that $f(n) \neq O(g(n))$, could you help me please? $\endgroup$ Jul 22 at 17:09
  • 1
    $\begingroup$ You can take $f(n)=\omega(g(n))$, as a result, $f(n)=\Omega(g(n))$ and $f(n)\neq \mathcal{O}(g(n))$ $\endgroup$
    – Jut
    Jul 22 at 17:10
  • $\begingroup$ Ok, thanks for that! $\endgroup$ Jul 22 at 17:17

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.