algorithm - Can Lower bound of Upper bound of f(n) equal Upper bound of Lower bound of f(n) -

assertion :

Ω(o(f(n))) = o(Ω(f(n)))

to disprove, need give counter example functions f(n),

so let f(n) = n assuming

k1 <= n <= k4 ; k1, k4, n > 0

thus :

o(n) = k4 ; k3 <= k4 <= k5 k3, k5 > 0

Ω(n) = k1 ; k0 <= k1 <= k2 k1, k2 > 0

now,

o(k1) = k2

Ω(k4) = k3

can state, k2 <= k3 hence assertion disapproved ?? if equal stands ??

your argument not correct because portion below;

k1 <= n <= k4 ; k1, k4, n > 0

you can not use numbers k1 , k4 prove or disapprove these relations because in asymptotic notations, should use function.

you can use below solution disapprove relation:

f(n) = n  h(n) = o(f(n)) => h(n) <= f(n)

i assume (counterexample)

h(n) = n

for right side of relation, assume that

f(n) = n  g(n) = Ω(f(n)) => f(n) <= g(n)

i assume (counterexample)

g(n) = log n

by replacing these functions in first relationship have;

Ω(o(f(n))) = o(Ω(f(n))) =>  Ω(h(n)) = o(g(n)) =>  Ω(n) = o(log n)

as same way, can assume:

k(n) = Ω(n)

i assume (counterexample)

k(n) = n

finally have:

Ω(n) = o(log n) =>  n = o(log n)

this result (n = o(log n)) not correct , first relationship not correct.

ANy