0
$\begingroup$

I am trying to teach myself asymptotic notations. I feel like I'm in over my head. I read the explanations in the text book, and Khan Academy. But when I try to do proofs, I can't grasp anything.

I'm trying to prove that If f (n) = ω(g(n)), then f (n) is not in O(g(n)) or o(g(n)).

I know that they don't intersect, as ω proves the lower bound (not tight) and O and o prove upper bounds. But I have no idea how to set up a proof to solve this.

Any help would be appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ In these cases the proofs are almost always just manipulations of the definitions. You want to prove an implication (which we observe by the if-then style of the statement). So first let $f\in \omega(g)$ and write out exactly what this means. Then show that $f\notin O(g)$ and $f\notin o(g)$ hint: one of these implies the other $\endgroup$
    – awillia91
    Commented Sep 5, 2023 at 17:02

1 Answer 1

0
$\begingroup$

With a simplified notation, $\omega$ holds if $\forall\,c:f>c\,g$, while $O$ holds if $\exists\,c: f\le c\,g$.

These are obviously contradictory statements.

$\endgroup$

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.