Algorithms with different complexity

Question

Can the complexity of an algorithm be at the time in O(n^2) and in O(n logn)? i am sure about this one. But what about in Ω(n^2) and in O(n logn), also and in Θ(n^2) and in Ω(n logn). Thanks

I think you are missing an important letter when you say and in (n logn)- did you mean to put an O, an Ω, or a Θ there before the parentheses? — David Robinson
– David Robinson, Commented Dec 25, 2012 at 17:43

David Robinson · Accepted Answer · 2012-12-25 18:24:00Z

5

Big-O notation refers only to the upper bound. Thus, if it is in O(n log n), it is necessarily in O(n^2) (since n^2 grows faster than n log n).
No, it cannot be in both Ω(n^2) and in O(n log n). That would mean "upper bounded by n log n and lower bounded by n^2, which is impossible.
Θ(n^2) means it is bounded both above and below by n^2, which necessarily means it is bounded below by Ω(n log n).

edited Dec 25, 2012 at 18:24

answered Dec 25, 2012 at 17:43

David Robinson

78.8k16 gold badges172 silver badges189 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

sully11 Over a year ago

thanks, but what about in Ω(n^2) and in O(n logn) it seems correct.

Collectives™ on Stack Overflow

Algorithms with different complexity

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related