Prove that
f
(
n
)
=
O
(
g
(
n
)
)
⟺
g
(
n
)
=
Ω
(
f
(
n
)
)
Proof Since
f
(
n
)
=
O
(
g
(
n
)
)
⟹
∃
constants
c
>
0
and
n
0
∈
N
such that
0
≤
f
(
n
)
≤
c
g
(
n
)
∀
n
≥
n
0
Dividing both side by
c
0
≤
(
1
/
c
)
f
(
n
)
≤
g
(
n
)
∀
n
≥
n
0
Put
1
/
c
=
c
′
0
≤
c
′
f
(
n
)
≤
g
(
n
)
∀
n
≥
n
0
Hence,
g
(
n
)
=
Ω
(
f
(
n
)
)
Mathbot Says...
I wasn't able to parse your question, but the HE.NET team is hard at work making me smarter.