Proving asymptotic relationships

Question

I am trying to teach myself asymptotic notations. I feel like I'm in over my head. I read the explanations in the textbook, 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.

Answer 1

What do these asymptotic notations mean formally? Start by writing out what they actually tell you. As an example (using your notation)

Let c be a real number with c>0. Since f(n)=Ω(g(n)) we know that there is a natural number n₀ such that for all n>n₀ , f(n) > c • g(n)

Now let's do the same for the consequents. First, what does it mean if f(n)=O(g(n))? It means that there exists constants c₁ and n₁ such that for all n>n₁, f(n)≤c₁•g(n)

Also if f(n)=o(g(n)) then for every real number c₂>0 there is a natural number n₂ such that for all n>n₂ f(n)<c₂•g(n)

We want to prove that if f=ω(g)) then f≠O(g) and f≠o(g). The easiest way to start is to prove a lemma 1 that if f≠O(g) then f≠o(g). We will prove the contrapositive.

Let f=o(g) and let c=1. Since f=o(g) there is a natural number n₀ such that for all n>n₀ f(n)<c•g(n). Then for this same n₀ and c we have for all n>n₀ f(n)≤c•g(n), so f=O(g) as required.

Then it is enough for us to prove that if f(n)=ω(g(n)) then f(n)≠O(g(n)). Let's proceed by contradiction.

Suppose f(n)=ω(g(n)) and f(n)=O(g(n)). Since f(n)=O(g(n)) there exist constants c and n₀ such that for n>n₀, f(n)≤c•g(n). Since f(n)=ω(g(n)) for that same value of c there exists a natural number n₁ such that for n>n₁ f(n)>c•g(n). Now let n₂ = max(n₀,n₁) then for n>n_2, f(n)>c•g(n) and f(n)≤c•g(n). This is our contradiction and we can conclude that if f(n)=ω(g(n)) then f(n)≠O(g(n)). After applying Lemma 1 we reach our desired conclusion: if f(n)=ω(g(n)) then f(n)≠O(g(n)) and f(n)≠o(g(n))