Searching
How fast are these searches?
- Sequential Search
- Binary Search
Given N Data items, how many secs does it take (assuming 109 instructions/sec)
| Number items N |
Binary Search O(log N) |
Sequential Search O(N) |
Quicksort O(N log N) |
Shellsort O(N(3/2)) |
Insertion Sort Selection Sort O(N2) |
|---|---|---|---|---|---|
| 10 | < sec | < sec | < sec | < sec | < sec |
| 100 | < sec | < sec | < sec | < sec | < sec |
| 1000 | < sec | < sec | < sec | < sec | < sec |
| 10,000 | < sec | < sec | < sec | < sec | < sec |
| 100,000 | < sec | < sec | < sec | < sec | 10 sec |
| 1,000,000 | < sec | < sec | < sec | 1 sec | 15 sec |
| 10,000,000 | < sec | < sec | < sec | 10 sec | 1 hour |
| 100,000,000 | < sec | < sec | 3 sec | 15 sec | 115 days |
| 1,000,000,000 | < sec | 1 sec | 30 sec | 1 hour | 31 years |
