O'Reilly logo
  • Garrett Maring thinks this is interesting:

Inspection of the algorithm reveals that statements 4, 5, and 9 will execute every time through the loop, as will either statements 6 or 8. Therefore the multiplier is four statements, and our refinement to the Big-O analysis of this algorithm would be to say its dominant speed term is 4(log2n − 1). Stated another way, this algorithm will locate an item in an n element array after executing, at worst, 4(log2n − 1) instructions as n gets large.


Cover of Data Structures and Algorithms Using Java


  1. the While-loop
    2.the if
  2. Either executes if or else
  3. return