Prove/disprove if f(n)=Ωg(n) then f(n)-g(n)=Ωmin(f(n),g(n))

173 Views Asked by At

i was thinking about doing something like this, but im not sure it is right if $f(n)=Ωg(n)$ then $f(n) > g(n)$ meaning $f(n) - g(n) >c*g(n)$ following $f(n) >(c+1)*g(n)$ and that is allready given.

is that the right course of action here, or am i making a mistake somewhere?

1

There are 1 best solutions below

0
On

Given that $f(n) = \Omega(g(n))$ doesn't imply $f(n) > g(n)$.
It rather implies that for some real number $n_0$ and positive real number $ c$, for every real number $n$ satisfying $n \geq n_0$,
$$|f(n)| \geq c \cdot |g(n)|$$ Because there are some cases of $f,g,n_0$ and $c$ such that $f(n) \geq c \cdot g(n)$ and $f(n) < g(n)$.
For example,
$n_0 = 2$
$c = \frac{1}{2}$
$f(n) = n-1$
and $g(n) = n$