CODEWITHSUNDEEP
time-complexitybig-o
Min
Min

Reputation: 528

Time complexity bounded by omega

Hi I was wandering if this statement is true.

if f(n) = omega(g(n)) and g(n) = omega(f(n))

does it mean that f(n) = theta(g(n)) or g(n) = theta(f(n))?

Could anyone clarify this for me?

Upvotes: 1

Views: 23

Answers (1)

libik
libik

Reputation: 23029

You can change these symbols for < > if you want. It is basically how it works in terms of complexity (not the algebra, therefore you cannot use the <> directly)

f(n) <= g(n)

g(n) <= f(n)

Yes, it means that g(n) = f(n) (in complexity, therefore you can read it as g(n) has same complexity as f(n))

In formal complexity world, you use Theta for that.

Upvotes: 2

Related Questions