title: Complexity of Binary Search
body: <p>I am watching the Berkley Uni online lecture and stuck on the below.</p>
  
  <p><strong>Problem</strong>: Assume you have a collection of CD that is already sorted. You want to find the list of CD with whose title starts with "Best Of."</p>
  
  <p><strong>Solution</strong>: We will use binary search to find the first case of "Best Of" and then we print until the tile is no longer "Best Of"</p>
  
  <p><strong>Additional question</strong>: Find the complexity of this Algorithm.</p>
  
  <p><em>Upper Bound</em>: Binary Search Upper Bound is O(log n), so once we have found it then we print let say k title. so it is O(logn + k)</p>
  
  <p><em>Lower Bound</em>: Binary Search lower Bound is Omega(1) assuming we are lucky and the record title is the middle title. In this case it is Omega(k)</p>
  
  <p>This is the way I analyzed it. </p>
  
  <p>But in the lecture, the lecturer used best case and worst case. 
  I have two questions about it:</p>
  
  <ol>
  <li>Why need to use best case and worst case, aren't big-O and Omega considered as the best and worst cases the algorithm can perform?</li>
  <li><p>His analysis was 
                  Worst Case : Theta(logn + k)<br>
                  Best Case : Theta (k)</p>
  
  <p>If I use the concept of Worst Case as referring to the data and having nothing to do with algorithm then yep, his analysis is right.
  This is because assuming the worst case (CD title in the end or not found) then the Big O and Omega is both log n there it is theta(log n +k).</p>
  
  <p>Assuming you do not do "best case" and "worst case", then how do you analyze the algorithm?  Is my analysis right?</p></li>
  </ol>