CODEWITHSUNDEEP
algorithmsortingperformance
Bernard
Bernard

Reputation: 4590

When big O or Omega or theta can be an element of a set?

I'm trying to figure out the efficiency of my algorithms and I have little bit confusion. Just need some expert idea to justify my answers or reference me to somewhere which is explaining about the being an element of not in asymptotic subject. (There is many resources but nothing about element of set is found by me)

When we say O(n^2) which is for two loops is it right to say:

n^2 is an element of O(n^3)

To my understanding big O is the worst case and omega is the best efficient case. If we put them on the graph all the cases of n^2 is part of O(n^3) so the first one is not right?

n^3 is an element of omega(n^2)

And also about the second one it is not right. Because some of the best cases of omega(n^2) is not in all the cases of n^3!

Finally is

2^(n+1) element of theta(2^n)

I have no idea how to measure that!

Upvotes: 0

Views: 1610

Answers (2)

Aravind
Aravind

Reputation: 3199

I will list the answers one by one.

1.) n^2 is an element of O(n^3)
True
To know more about Big-Oh read here.

2.) n^3 is an element of omega(n^2)
True
To understand omega notation read here.

3.) 2^(n+1) element of theta(2^n)
True
By now you would know why this is right.(Hint:Constant factor)

Please ask if you have any more questions.

Upvotes: 2

MSalters
MSalters

Reputation: 179991

Big O, omega, theta in this context are all complexities. It's the functions with those complexities which form the sets you're thinking of.

Indeed, the set of functions with complexity O(n*n) is a subset of those with complexity O(n*n*n). Simply said, that's because O(n*n*n) means that the complexity is less than c*n*n*n as n goes to infinity, for some constant c. If a function has actual complexity 3*n*n + 7*n, then its complexity as n goes to infinity is obviously less than c*n*n*n, for any c.

Therefore, O(n*n*n) isn't just "three loops", it's "three loops or less".

Ω is the reverse. It's a lower bound for complexity, and c*n*n is a trivial lower bound for n*n*n as n goes to infinity.

The set of functions with complexity Θ(n*n) is the intersection of those with complexities O(n*n) and Ω(n*n). E.g. 3*n doesn't have complexity Θ(n*n) because it doesn't have complexity Ω(n*n), and 7*n*n*n doesn't have complexity Θ(n*n) because it doesn't have complexity O(n*n).

Upvotes: 4

Related Questions