Binary Search

1. Big O of Binary Search:

   To calculate the worst-case Big O for Binary Search for an array of size n consider the following:
   After 1 iteration,s there are n/2¹ (n/2) elements left to search.
   After 2 iterations, there are n/2² (n/2/2) elements left to search.
   After 3 iterations, there are n/2³ (n/2/2/2) elements left to search.
   After 4 iterations, there are n/2⁴ (n/2/2/2/2) elements left to search.
   After k iterations, there are n/2^k elements left to search.
   In the worst case, searching stops when there is 1 element left to search, so n/2^k = 1
   Rearranging the equation: 2^k = n
   Taking the log of both sides: log₂ 2^k = log₂ n
   Simplifying: k log₂ 2 = log₂ n
   Simplifying: k = log₂ n
   
   Requires log₂ n steps/iterations, therefore the O( log₂ n ) = O( log n )

Last Modified: