Efficiency
Different algorithms devised to solve the same problem often differ dramatically in their efficiency. These differences can be much more significant than differences due to hardware and software.
As an example, in Chapter 2, we will see two algorithms for sorting. The first, known as insertion sort, takes time roughly equal to c1n2 to sort n items, where c1 is a constant that does not depend on n. That is, it takes time roughly proportional to n2. The second, merge sort, takes time roughly equal to c2n lg n, where lg n stands for log2 n and c2 is another constant that also does not depend on n. Inser- tion sort typically has a smaller constant factor than merge sort, so that c1 < c2. We shall see that the constant factors can have far less of an impact on the running time than the dependence on the input size n. Let’s write insertion sort’s running time as c1n n and merge sort’s running time as c2n lg n. Then we see that where insertion sort has a factor of n in its running time, merge sort has a factor of lg n, which is much smaller. (For example, when n D 1000, lg n is approximately 10, and when n equals one million, lg n is approximately only 20.) Although insertion sort usually runs faster than merge sort for small input sizes, once the input size n becomes large enough, merge sort’s advantage of lg n vs. n will more than com- pensate for the difference in constant factors. No matter how much smaller c1 is than c2, there will always be a crossover point beyond which merge sort is faster.
1 of 2
For a concrete example, let us pit a faster computer (computer A) running insertion sort against a slower computer (computer B) running merge sort. They each must sort an array of 10 million numbers. (Although 10 million numbers might seem like a lot, if the numbers are eight-byte integers, then the input occupies about 80 megabytes, which fits in the memory of even an inexpensive laptop computer many times over.) 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 insertion sort in machine language for computer A, and the resulting code requires 2n2 instructions to sort n numbers. Suppose further that just an average programmer implements merge sort, using a high-level language with an inefficient compiler, with the resulting code taking 50n lg n instructions. To sort 10 million numbers, computer A takes
2 .107/2 instructions D 20,000 seconds (more than 5.5 hours) ; 1010 instructions/second
while computer B takes
1.2 Algorithms as a technology 13
50 107 lg 107 instructions 1163 seconds (less than 20 minutes) : 107 instructions/second
By using an algorithm whose running time grows more slowly, even with a poor compiler, computer B runs more than 17 times faster than computer A! The advantage of merge sort is even more pronounced when we sort 100 million numbers: where insertion sort takes more than 23 days, merge sort takes under four hours. In general, as the problem size increases, so does the relative advantage of merge sort.
nobody on /g/ can understand this stuff. that's why you're all dumb, desktop thread posters.
lol computers
Next-level computer science here....
Damn, I feel stupid.
So essentially you're paying for the quality of the operating system and not the hardware?
what a fucking retarded comparison, who wrote this?
>>52098208
Bill Schiller Stallman
Why don't u screw osx and windump and install a Linux distribution. :-) ;D
>>52098254
because it's even more laughably inefficient than windows
have a look at the source for yourself
>>52098308
B-but, how do I compare it to the asintotic eficiency of Windows or OSX senpai? I don't the source code for those (except Darwin kernel)
Pretty sure OSX uses bogosort.
It does have a best-case scenario that runs in O(n), after all.
>>52098308
Doesn't matter. I/O bottlenecks everything.
*cough* HFS+ *cough* NTFS
>>52097068
not sure if trolling
>>52097068
tl;dr
I don't really care. Gayming is for Windows, software I use at work is for Windows too, shitposting is comfy enough even on a cheap android tablet.
I don't see a single reason to buy Apple products, since I don't give a fuck about meme status symbols.
