How a Smart Algorithm Can beat a Great Hardware?
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 amounts of 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
The 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.
The 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 the internal design of an 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, interpolating addresses etc.
We intend to solve larger and larger problems with ever-increasing hardware capacity. The impact of the efficient algorithm is multiplied across both larger problems, just as we discussed above. The well-developed merge sort easily beats 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 knowledge of the algorithm.
Additional Reading: How algorithm makes a system smart?
Short Questions
Q: What is the time complexity of insertion sort?
Insertion sort runs in O(n2) time
Q: What is the time complexity of merge sort?
Merge sort runs in O(nlogn) time