# When the data size and processor speed are both multiplied by 10, then a linearithmic algorithm takes double the time to finish?

Robert Sedgewick mentioned, if a computer can handle 10x data and the processor is also 10x as fast, then a $$O(n^2)$$ algorithm actually runs slower than before.

Is this the correct idea when a computer has 10x RAM and can handle 10x data all at once, and also have a processor that is 10x faster, then:

1. A $$O(n^2)$$ solution is slower, because now $$n^2$$ is 100 times, but processor is only faster by 10 times. So the time it takes to solve the problem is 10 times more. So if it took 1 hour to solve the problem before, now it would take 10 hours.

2. If it is a $$O(n \log n)$$ solution, then roughly speaking, for $$n \log n$$, it is

$$(100 \log 100) / (10 \log 10) = (100 / 10) \times (\log 100 / \log 10) = 10 \times log_{10} 100 = 20$$

and since the processor is 10 times as fast, that means now the algorithm is "half as fast"? (meaning if it took 1 hour to solve the whole problem before, now it would take 2 hours)

• Try n = 1,000,000 instead of n = 100. – gnasher729 Aug 27 '19 at 11:29
• in terms of calculation, using 100 vs 10, or using 10,000,000 vs 1,000,000 I think is the same – nopole Aug 27 '19 at 23:44

• I think what Robert Sedgewick was saying is something like this: if you are in some research or solving some kind of problem, in the past, you might only dare to have sample data, say 100,000 or 1,000,000, but now with a computer having 10x the RAM and 10x as fast processor (say, from 400MHz to 4GHz), then you dare to increase the sample data to 1,000,000 or even 10,000,000 -- that's what he meant. And then you find that if you have a $O (n^2)$ solution, it actually takes 10 times the duration to solve it as before – nopole Aug 27 '19 at 11:59