1

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)?

Saloni Agrawal
  • 57
  • 1
  • 7
  • 2
    In the best case you still have to scan the whole input to determine if it *is* sorted. – jonrsharpe Dec 22 '19 at 19:39
  • 2
    It's not clear if you're saying you think Theta(n) is correct as opposed to O(n), or something else. By the way, not every sorting algorithm has the best case when the array is already sorted. For example, a sorted array is the worst-case for quicksort if you always choose the first element as the pivot. – kaya3 Dec 22 '19 at 19:44
  • @kaya3 I mean Theta(n) should be written instead of O(n) for bubble sort. – Saloni Agrawal Dec 22 '19 at 20:48
  • @jonrsharpe Can you please elaborate more since scanning the whole input doesn't guarantee O(n). – Saloni Agrawal Dec 22 '19 at 20:55
  • 1
    Theta(n) is a subset of O(n), so if a function is in Theta(n) then it is also in O(n). – kaya3 Dec 22 '19 at 21:55
  • Does this answer your question? [how to calculate Bubble sort Time Complexity](https://stackoverflow.com/questions/29555839/how-to-calculate-bubble-sort-time-complexity) – Bob Jarvis - Слава Україні Dec 23 '19 at 12:26

1 Answers1

2

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.

trincot
  • 317,000
  • 35
  • 244
  • 286