Still not understanding Big-O vs Worst Case Time Complexity

user_3042018 0
Viewed 555

The worst case for time taken by linear search is when the item is at the end of the list/array, or doesn't exist. In this case, the algorithm will need to perform n comparisons, to see if each element is the required value, assuming n is the length of the array/list.

From what I've understood of big-O notation, it makes sense to say that the time complexity of this algorithm is O(n), as it COULD happen that the worst case occurs, and big-O is used when we want to make a conservative estimate of the "worst case".

From a lot posts and answers on Stack Overflow, it seems this thinking is flawed, with claims made such as Big-O notation has nothing to do with the worst case analysis.

Please help me to understand the distinction in a way that doesn't just add to my confusion, as the answers here: Why big-Oh is not always a worst case analysis of an algorithm? do.

I'm not seeing how big-O has NOTHING to do with worst case analysis. From my current hilltop, it looks like big-O expresses how the worst case grows as the input size grows, which seems very much "to do" with worst-case analysis.

Statements such as this, from https://medium.com/omarelgabrys-blog/the-big-scary-o-notation-ce9352d827ce :

As an example, worst case analysis gives the maximum number of operations assuming that the input is in the worst possible state, while the big o notation express the max number of operations done in the worst case.

don't help much, as I cannot see what distinction is being referred to.

Any added clarity much appreciated.

linear-search time-complexity algorithm
2 Answers

The big-O notation is indeed independent of the worst-case analysis. It applies to any function you want.

In the case of a linear seach,

  • the worst-case complexity is O(n) (in fact even Θ(n)),

  • the average-case complexity is O(n) (in fact even Θ(n)),

  • the best-case complexity is O(1) (in fact even Θ(1)).

So big-O and worst-case are different concepts, though a big-O bound for the running time of an algorithm must hold for the worst-case.

user_11965490

This is the case:

If an algorithm to find a solution for a problem is in O(f(n)), means that the worst-case scenario for finding the solution for the problem by the algorithm is in O(f(n)). In other words, if the worst-case scenario can be found in g(n) steps by the algorithm, then g(n) is in O(f(n)).

For example, for the search algorithm, as you have mentioned, we know that the worst-case scenario can be found in O(n). Now, although the algorithm is in O(n), we can say the algorithm is in O(n^2) as well. As you see, here is the distinction between Big-Oh complexity and the worst-case scenario.

In sum, the worst-case scenario complexity of an algorithm is a subset of the Big-Oh complexity of the algorithm.

user_37688710
Related