On this page, you will compare the time required for binary search and for linear search.
binary search
block, but it uses the linear algorithm.
linear search
takes to find the word "zebra" in each length list.
Length of List | Linear Search Time |
---|---|
1000 | |
10,000 | |
100,000 |
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 is called).
linear search
algorithm for each length list?
Length of List | Linear Search Time |
Linear Search Steps |
---|---|---|
1000 | ||
10,000 | ||
100,000 |
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.
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.
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 |
linear search
and the binary search
algorithm, and compare the two search algorithms: