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.
- the While-loop
- Either executes if or else
Share this highlighthttp://www.safaribooksonline.com/a/data-structures-and/54398/