CODEWITHSUNDEEP
algorithmsortingdata-structuresbubble-sort
Saloni Agrawal
Saloni Agrawal

Reputation: 57

Time Complexity of Bubble Sort

Time complexity of Bubble Sort during best case is explained as O(n) and not Theta(n)? Isn't that wrong since best case can be defined as: Best case = fastest time to complete, with optimal inputs chosen.( For example, the best case for a sorting algorithm would be data that's already sorted.). Edit:-I have seen other questions on stack overflow and other resources which are based on time complexity of bubble sort during best case.They all are explaining it as O(n),I had question why the best case time complexity is written as O(n) instead of Theta(n)?

Upvotes: 1

Views: 1638

Answers (1)

trincot
trincot

Reputation: 350137

You may use O(f) or θ(f) for lots of cases. One is free to use it for best case, worst case, average case, or any other case you can define.

O(f) represents an asymptotically upper bound for the case one describes. So for instance, you can even say that bubble sort is O(n10) -- although that is not very useful information, and one would expect to use the most bounding function instead, i.e. O(n2) -- and you can also say that in the best case bubble sort is O(n).

θ(f) sets an asymptotically upper and lower bound for the case one describes. So it cannot always be used when the upper and lower bound are not the same. For instance, one cannot say that bubble sort is θ(n2), nor that it is θ(n): it just doesn't have such a tight bound. If you would take Merge Sort, then there is such a tight bound: it has a time complexity of θ(nlogn)

However, when you limit bubble sort to the best case(s) only, you can use Theta: best case for bubble sort is θ(n).

Note that by nature of the words "worst" and "best", you can always use Theta notation to describe the corresponding complexity (at least when it is known). On the other hand, you are not required to use it. You may as well use the O notation.

In practice one may often assume that the use of O(f) for a worst or best case of an algorithm, intends to give the lowest bound possible. And in that case it is indeed also θ(f).

Whatever is θ(f) is also O(f), but not necessarily vice versa.

Upvotes: 2

Related Questions