Proving Order of complexity proofs if f(n) is Ω(n∗g(n)), then f(n) is not O(g(n))

user_14411019 0
Viewed 350

Show that if f(n) is Ω(n∗g(n)), then f(n) is not O(g(n))

Assume f(n) is Ω(n ∗ g(n)) and f(n) is O(g(n)). Need to show a contradiction. The approach is to find a value of n that violates the definitions. Proof: f(n) is Ω(n ∗ g(n)) implies there exists positive values C and k such that n > k implies f(n) ≥ C ∗ n ∗ g(n). f(n) is O(g(n)) implies there exists positive values C′ and k′ such that n > k′ implies f(n) ≤ C ∗ g(n).

So what value of n violates the definition and how can I show a contradiction?

big-o time-complexity algorithm
1 Answers

Your approach to prove the statement by contradiction is possible. But first of all, you need to be a bit more precise:

  1. f and g are positive non-decreasing functions on integers
  2. C and C' are >= 0
  3. Your last implication should read C' * g(n) (as opposed to C * g(n)).

So we start with:

(a) There exist positive integers C, C', k, k' such that for all n > k and n' > k':

C * n * g(n) <= f(n) and f(n') <= C' g(n')

By chaining together your two implications and merging the two universal quantifiers into one (by noting that for all n > k and n' > k' implies for all n > max(k,k')), you immediately get:

(b) There exist positive integers C, C', k, k' such that for all n > max(k,k'):

C * n * g(n) <= C' g(n)

Dividing by g(n) on both sides, which is valid by assumption 1. above, yields the equivalent:

(c) There exist positive integers C, C', k, k' such that for all n > max(k,k'):

C * n <= C'

This is equivalent to:

(d) There exist positive integers C, C', k, k' such that for all n > max(k,k'):

n <= C'/C

The last statement is equivalent to false. This is a contradiction and hence the original statement is true.

user_6899230
Related