Smart algorithms do intelligent work and easily outperform hardware technologies. In this article, we will look at a specific scenario in which a cleverly designed algorithm outperforms hardware. Algorithms have evolved over time, from primitive to very efficient.
Different algorithms take different time to solve the same problem. This gap in algorithmic processing may be more important than the difference in machine hardware and software architectures.
Effect of Smart Algorithm
Consider a faster computer A (executes 1010 instructions/ second) and slower computer B (executes 107 instructions / second).
Insertion sort runs in quadratic order of input size i.e. c1.n2, and merge sort runs in c2.nlogn time.
Let us schedule insertion sort on computer A with c1 = 2, and merge sort on computer B with c2 = 50.
Consider the problem of size n = 107.
Running time of insertion sort on computer A would be,
((2 x 107)2 instructions) / (1010 instructions / seconds) = 20,000 seconds
Running time of merge sort on computer B would be,
(50 x 107 log 107 instructions) / (1010 instructions / seconds) = 1, 163 seconds
Even with poor hardware, the efficient algorithm runs 17 times faster than the poor algorithm on faster hardware. Advantage amplifies when the input instance is even bigger. For 100 million numbers, merge sort takes under four hours, whereas insertion sort takes more than 23 days.
Analysis and Discussion
Above illustration is sufficient to prove the importance of the design of a proper algorithm. For efficiency analysis, algorithm complexity should be evaluated for a large program instance.
Choice of the algorithm is as important as choosing the hardware, and hence the algorithm should also be considered as technology just like hardware.
Mathematicians are improving algorithms at a pace researchers are improving the physical hardware.
Some applications do not require algorithmic efficiency at the application level, but internally design of efficient algorithm has a great deal.
Consider the application that determines the route to travel from one location to the other. An implementation may rely on fast hardware, wide area networking, and a possible programming language. Even in such applications also, algorithms would be useful in determining the route, rendering the graphics and interpolating addresses etc.
We intend to solve larger and larger problems with ever-increasing hardware capacity. The impact of the efficient algorithm is multiplied both larger problem, just we discussed above. Well-developed merge sort easily beat the insertion sort running on superior hardware.
Solid knowledge of algorithms separates the truly skilled programmer from the novice. We can accomplish our tasks without knowing much about algorithms, but we can do it much more efficiently with the knowledge of the algorithm.
Additional Reading: How algorithm makes a system smart?