proof for small o order relation with big o and omega.

45 Views Asked by At

I am trying to understand small o's relation from theorem below:

If $g(n) \in o(f(n))$, then $$g(n)\in O(f(n))-\Omega(f(n)).$$ Proof : Because $g(n)\in o(f(n))$, for every positive real constant $c$ there exists an $N$ such that, for all $n\ge N$, $$g(n)\le c\times f(n),$$ which means that the bound certainly holds for some $c$. Therefore, $$g(n)\in O(f(n)).$$ We will show that $g(n)$ is not in $\Omega(f(n))$ using proof by contradiction. If $g(n)\in\Omega(f(n))$, then there exists some real constrant $c>0$ and some $N_1$ such that, for all $n\ge N_1$, $$g(n)\ge c\times f(n).$$ But, because $g(n)\in o(f(n))$, there exists some $N_2$ such that, for all $n\ge N_2$, $$g(n)\le\frac{c}{2}\times f(n).$$ Both inequalities would have to hold for all $n$ greater than both $N_1$ and $N_2$. This contradiction proves that $g(n)$ cannot be in $\Omega(f(n))$.

(Foundations of Algorithms 5th edition, Richard Neapolitan, 9781284049190)

What I don't understand is why $f(n)$ is multiplied by $\frac{c}{2}$ instead of just $c$ when $g(n)$ is a set of small o.

If it wasn't $\frac{c}{2}$, but just $c$ was multiplied, then it would be easy to see that it's contradictory because for $n$ greater than $N_1$ and $N_2$, both must satisfy that it should be greater than or less than $c\times f(n)$.

So, Why is $\frac{c}{2}$ multiplied? Can't it just be a $c$?

1

There are 1 best solutions below

0
On BEST ANSWER

If just $c$ was multiplied, then there would have been no contradiction since it can happen that $$g(n)= c\times f(n)\text{ for all } n$$ for all $n>0$, which means both $$g(n)\ge c\times f(n)\text{ for all }n\ge N_1$$ and $$g(n)\le c\times f(n)\text{ for all }n\ge N_2.$$


On the other hand, we can use $\frac c{533680}$, $0.999c$, etc. instead of $\frac c2$ to multiply $f(n)$ for the sake of a contradiction.