I am a little confused in a specific case with the Big O notation and the Asymptotic behavior of algorithms. While I was reading the blog http://discrete.gr/complexity/ that describes these notations very well I came across this statement whether it is true or false:
A O( n ) algorithm is Θ( 1 )
The answer says that this may or may not be true depending on the algorithm. In the general case it's false. If an algorithm is Θ( 1 ), then it certainly is O( n ). But if it's O( n ) then it may not be Θ( 1 ). For example, a Θ( n ) algorithm is O( n ) but not Θ( 1 ).
I am trying a little hard to comprehend this answer. I understand that Big O implies that a program can asymptotically be no worse. So I interpret that above statement where O( n ) is worse than Θ( 1 ) and is true.
Can someone explain with an example?
Consider the optimized bubble sort, which has an asymptotically tight upper bound of O(n2), and an asymptotically tight lower bound of Ω(n) (when the array is already sorted). The arrangement of items determines how many operations the algorithm will have to perform.
Contrast that to summing a list of integers. In this case, you always have to look at each item in the list exactly once. The upper bound is O(n), and the lower bound is Ω(n). There is no arrangement of items that will change the complexity of the algorithm. In this case, when the tight upper and lower bounds are the same, we say that the algorithmic complexity is Θ(n).
If an algorithm is Θ(n), then the complexity will never exceed O(n), and it will never be less than O(n). So it can't possibly be O(1) or Θ(1).
But if an algorithm is described as O(n), it could be Ω(1). For example, finding the first non-zero value in a list of integers. If the first item in the list is non-zero, then you don't have to look at any other numbers. But if the list is all zeroes, you end up looking at them all. So the upper bound is O(n) and the lower bound is Ω(1).