Algorithms are just like a technology. We all use latest and greatest processors but we need to run implementations of good algorithms on that computer in order to properly take benefits of our money that we spent to have the latest processor. Let’s make this example more concrete by pitting a faster computer(computer A) running a sorting algorithm whose running time on n values grows like n2 against a slower computer (computer B) running a sorting algorithm whose running time grows like n lg n. They each must sort an array of 10 million numbers. Suppose that computer A executes 10 billion instructions per second (faster than any single sequential computer at the time of this writing) and computer B executes only 10 million instructions per second, so that computer A is 1000 times faster than computer B in raw computing power. To make the difference even more dramatic, suppose that the world’s craftiest programmer codes in machine language for computer A, and the resulting code requires 2n2 instructions to sort n numbers. Suppose further that just an average programmer writes for computer B, using a high level language with an inefficient compiler, with the resulting code taking 50n lg n instructions.
Computer A (Faster) :
Running time grows like n^2.
10 billion instructions per sec.
2n^2 instruction.
Computer B(Slower) :
Grows in nlogn.
10 million instruction per sec
50 nlogn instruction.
Post a Comment