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

Question

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 ??

Answer 1

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).