When is Big-Oh (n) = Omega (n)? Is this the same as theta (n)?

Yes, you are right if f is BigO(g)

and f is Omega(g)

then f is BigTheta(g)

. In fact, this is just the definition BigTheta

.

To apply this to algorithms, if the algorithm is both BigO(n^2)

, and Omega(n^2)

, for example, this BigTheta(n^2)

. And if it is BigTheta(n^2)

, then there is BigO(n^2)

and Omega(n^2)

.