Binary search complexity

Question

I am watching an online lecture by Berkley Uni and stick with it below.

Problem . Suppose you have a CD collection that is already sorted. You want to find a list of CDs whose title begins with "Best Of."

Solution . We will use a binary search to find the first “Best Of” case, and then we print until the tile stops “Best”

Additional question : find the complexity of this algorithm.

Upper bound: Binary Search Upper Bound - O (log n), so as soon as we find it, we will type let say k title. so this is O (logn + k)

Lower Bound: Binary Search lower Bound - Omega (1), believing that we are lucky, and the title of the record is the average title. In this case, this is Omega (k)

That's how I analyzed it.

But in the lecture, the lecturer used the best case and worst case. I have two questions:

• Why is it necessary to use the best case and the worst case, are not large-O and Omega considered the best and worst cases that the algorithm can execute?

• His analysis was the Worst Case: Theta (logn + k)
  Best case: Theta (k)

  If I use the concept of the worst case as data-related and not related to the algorithm, then yep, his analysis is right. This is because assuming the worst case (the name of the CD at the end or not found), then Big O and Omega are both log n there, this is theta (log n + k).

  Assuming you are not doing the “best case” and “worst case”, then how do you analyze the algorithm? Is my analysis correct?

Answer 1

Why use the best case and the worst case, are not large O and Omega are considered the best and worst cases that the algorithm can execute?

No, the notations Ο and Ω describe only the boundaries of the function that describes the asymptotic behavior of the actual behavior of the algorithm. Heres good

• Ω describes the lower bound : f (n) ∈ Ω (g (n)) means that the asymptotic behavior of f (n) is at least g (n) · k for some positive k, therefore f (n) is always not less than g ( n)
• Ο describes the upper bound : f (n) ∈ Ο (g (n)) means that the asymptotic behavior of f (n) is at most g (n) k for some positive k; therefore, f (n) is always no more than g (n) · k.

These two can be used both in the best case and in the worst case for binary search:

• best case: the first element you are looking at is the one you are looking for
  • Ω (1): You need at least one search
  • Ο (1): you need at most one type of search
• worst case: no item
  • Ω (log n): you need at least log n steps until you can say that the element you are looking for is missing
  • Ο (log n): you need no more than log n steps until you can say that the item you are looking for is missing

You see that the values ​​of Ω and Ο are identical. In this case, you can say that the dense estimate for the best case is Θ (1), and for the worst case, Θ (log n).

But often we want to know only the upper bound or tight binding, since the lower bound does not have much practical information.

Assuming you are not doing the “best case” and “worst case”, then how do you analyze the algorithm? Is my analysis correct?

Yes, your analysis seems correct.

Answer 2

For your first question, there is a difference between the best version of the algorithm, the worst execution time of the algorithm, big-O and big- & Omega; notation. The best and worst run times of the algorithm are actual mathematical functions with exact values ​​that show the maximum and minimum amount of work of the algorithm. To describe the growth rate of these functions, we can use big-O and big- & Omega; notation. However, you can describe the best behavior of a function with big and omega; designation or worst case with designation "big O". For example, we might know that the worst execution time of a function can be O (n ² ), but actually does not know which function O (n ² ) is the worst behavior. This can happen if we want to associate the worst behavior with the upper limit, so that we know that this is not catastrophically bad. It is possible that in this case the worst case behavior is actually & Theta; (n), and in this case O (n ² ) is a bad upper limit, but, saying that the worst behavior of O (n ² ) in this case indicates that it is not scary. In the same way, we can say that the best behavior of the algorithm is & Omega; (n) for example, if we know that he should do at least linear work, but cannot say whether he should do much more than that.

As for your second question, the analysis of the worst and best behavior of the algorithm depends entirely on the structure of the input data, and it is usually quite difficult to analyze the behavior of the best and worst case of the algorithm without seeing how it works on different data sets. It is perfectly reasonable to analyze the worst case by presenting some specific families of input data (note that this should be a family of inputs, not just one input, since we need to get an asymptotic estimate) and showing that the algorithm should perform poorly on this input. Similarly, you can analyze the best case.

Hope this helps!