CODEWITHSUNDEEP
complexity-theorytime-complexityspace-complexity
pa1geek
pa1geek

Reputation: 268

when is Big-Oh(n) = Omega(n) ? Is it same as theta(n)?

This question looks simple to me, but just wanted to see whether i am moving in the right direction.

Is it as simple as saying when n =1 ??

Upvotes: 3

Views: 191

Answers (1)

sch
sch

Reputation: 27506

Yes, you are correct, if f is BigO(g) and f is Omega(g) then f is BigTheta(g). In fact, this is exactly the definition of BigTheta.

To apply that to algorithms, if an algorithm is both BigO(n^2) and Omega(n^2) for example, then it is BigTheta(n^2). And if it is BigTheta(n^2) then is is BigO(n^2) and Omega(n^2).

Upvotes: 2

Related Questions