Exactly How Much Faster Is Binary Search?

TG and solutions need to be checked. --MF, 12/19/18

On this page, you will compare the time required for binary search and for linear search.

TG: Students compare these two algorithms in two ways: empirically (with clock time) and by counting operations (steps).
  1. AAP-2.P.3
    Locate the linear search for () in 'list input slot' block included in your project, and look inside it. Compare it to the algorithm you used to count the number of five- or seven-letter words. This block does the same computation as the binary search block, but it uses the linear algorithm.
  2. Use computation time of 'grey ring input slot' to test how much time linear search takes to find the word "zebra" in each length list.
    Length of List Linear Search Time
    1000
    10,000
    100,000
  3. Talk with Your Partner Look at the table. How would you describe what happens to the time as the input gets bigger?

The actual amount of physical time that it takes to solve a problem depends not only on your algorithm but also on how fast your computer is and what other programs you have running, etc. Therefore, computer scientists who want to measure the speed of an algorithm do it in terms of the number of steps. For example, what we really want to know about the efficiency of the linear search algorithm is how many times current item is compared to value (that is, how many times (current item) = (value) is called).

  1. AAP-2.P.3
    Add another column to your table. Assuming "zebra" is the last word in each word list, how many comparisons are made by the linear search algorithm for each length list?
    Length of List Linear Search Time Linear Search Steps
    1000
    10,000
    100,000
  2. Talk with Your Partner How would you describe what happens to the number of steps as the input list gets bigger? Write your hypothesis about the pattern.
  3. Does what happens with steps match what happens with time? That is, can you count steps as a measure of time?
: Efficiency
AAP-4.A.3

The relationship between the input size and the number of steps required to solve a problem is the efficiency of the algorithm used to solve the problem.

AAP-4.A.4, AAP-4.A.5

Counting the number of steps, as you just did, is an informal, but perfectly good way to determine the efficiency of an algorithm. The formal measurement of an algorithm requires a mathematical proof.

In this course, you are mostly working with small problems, so it doesn't matter how efficient the algorithm is. But in the real world, programmers deal with lists of billions of items, so the efficiency of an algorithm can make a huge difference.
  1. AAP-2.P part a
    AAP-2.P.3
    Now, test how much time binary search takes to find the word "zebra" in the sorted lists, and determine how many comparisons are made by the algorithm if "zebra" is the last word in each length list.
    Length of List Binary Search Time Binary Search Steps
    1000
    10,000
    100,000
  2. Talk with Your Partner Describe what happens to the time and the number of steps as the input list gets bigger. Write down your hypothesis.
  3. AAP-2.P.3, AAP-4.A.6
    Look back at your tables for the linear search and the binary search algorithm, and compare the two search algorithms:
    1. Which has more blocks in its code?
    2. Which runs faster for large inputs?
    3. Which algorithm is more efficient?
  4. AAP-2.P part b
    Write Out Your Thoughts What are the two requirements to use a binary search?