0
$\begingroup$

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)

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

I don't like how you expressed this - the ten times faster computer is ten times faster. It will solve the same problem and answer the same question ten times faster. Of course if you give it a question that would take 100 times longer on the old computer, then it will take only 10 times longer on the new computer.

If you had an algorithm that took n log n microseconds (and in CS "log" usually means log base 2) to solve a problem of size n, a problem of size 10 n would take 10n log (10n) microseconds on the old computer, and n log(10n) microseconds on the new computer.

log (10n) isn't ten times or twice as much as log n - the factor 10 turns into a constant. log (10n) = log n + log 10 ≈ log n + 3.3. If n = 10 it's twice as much. If n = 10 billion it's only ten percent more.

Two things to consider: No computer is just "ten times faster". A computer does many different kinds of operations. Some may be ten times faster, some even more, some less. And Big-O is concerned about asymptotic values: I could have an algorithm that takes on my computer n^2 microseconds if n ≤ 1,000,000 and 10n^2 microseconds if n > 1,000,000. So if you want to find actual execution times, you need more than Big-O.

And it is very common that actual execution times are quite different from what Big-O makes you belief when n is small. For example, let f(n) = n + 1000 log n. f(n) = O(n). But for n ≤ 10,000 f doesn't behave very linear at all.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – nopole Aug 27 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.