With computer power being doubled every 18 months as Moore's Law states, why do I care about algorithm efficiency as long as the algorithm is accurate?
Waaa, well let's look at the following real testing benchmark run on Intel Core-i7 2.8GHz
Table 1. Typical Algorithm Performance Benchmark (in second)
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
Size of problem | BinarySearch | LinearSearch | QuickSort | MergeSort | HeapSort | InsertSort | BubbleSort | Hanoi Tower
(n) | O(logn) | O(n) | O(nlogn) | O(nlogn) | O(nlogn) | O(n^2) | O(n^2) | O(2^n)
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
10 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 0.001 / 0.5 hour*
20 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 0.076 / 12 days*
32 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | ~0 | 175.171 / 136 years*
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
1,000 | ~0 | 0.000 | 0.000 | 0.001 | 0.001 | 0.007 | 0.008 |
10,000 | ~0 | 0.000 | 0.015 | 0.003 | 0.008 | 0.022 | 0.166 |
100,000 | ~0 | 0.000 | 0.023 | 0.034 | 0.024 | 1.505 | 16.119 |
1,000,000 | ~0 | 0.001 | 0.151 | 0.202 | 0.214 | 151.941 | 1,598.389 |
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
10,000,000 | 0.000 | 0.005 | 1.543 | 2.012 | 3.123 |17,736.500 | |
100,000,000 | 0.000 | 0.042 | 17.382 | 22.152 | 46.136 | | |
1,000,000,000 | 0.000 | 0.372 | | | | | |
----------------+--------------+--------------+-----------+-----------+----------+------------+------------+---------------------
* Note: If it were done by human with moving speed of 1 disk per second.
