efficient but how do we count the number of stepsfor examplethe number of times that either algorithm goes through its main loop will depend on the particular inputs we have already guessed that the advantage of binary search increases as the size of the list increases computer scientists attack these problems by analyzing the number of steps that an algorithm will take relative to the size or difficulty of the specific problem instance being solved for searchingthe difficulty is determined by the size of the collection obviouslyit takes more steps to find number in collection of million than it does in collection of ten the pertinent question is how many steps are needed to find value in list of size we are particularly interested in what happens as gets very large let' consider the linear search first if we have list of ten itemsthe most work our algorithm might have to do is to look at each item in turn the loop will iterate at most ten times suppose the list is twice as big then we might have to look at twice as many items if the list is three times as largeit will take three times as longetc in generalthe amount of time required is linearly related to the size of the list this is what computer scientists call linear time algorithm now you really know why it' called linear search what about the binary searchlet' start by considering concrete example suppose the list contains sixteen items each time through the loopthe remaining range is cut in half after one passthere are eight items left to consider the next time through there will be fourthen twoand finally one how many times will the loop executeit depends on how many times we can halve the range before running out of data this table might help you to sort things outlist size halvings can you see the pattern hereeach extra iteration of the loop doubles the size of the list if the binary search loops timesit can find single value in list of size each time through the loopit looks at one value (the middlein the list to see how many items are examined in list of size nwe need to solve this relationshipn for in this formulai is just an exponent with base of using the appropriate logarithm gives us this relationshipi log if you are not entirely comfortable with logarithmsjust remember that this value is the number of times that collection of size can be cut in half okso what does this bit of math tell usbinary search is an example of log time algorithm the amount of time it takes to solve given problem grows as the log of the problem size in the case of binary searcheach additional iteration doubles the size of the problem that we can solve you might not appreciate just how efficient binary search really is let me try to put it in perspective suppose you have new york city phone book withsaytwelve million names listed in alphabetical order you walk up to typical new yorker on the street and make the following proposition (assuming their number is listed)" ' going to try guessing your name each time