StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>An increase in hardware performance will give you a constant C times the running time of your algorithm. Meaning if you have computer A which is overall 2 times slower than computer B. Than your algorithm will be twice as fast on computer B. Twice as fast though really makes hardly no difference when you consider big input values to an algorithm though. </p> <p><a href="http://en.wikipedia.org/wiki/Big_O_notation" rel="nofollow noreferrer">In big O notation</a> that is to say you will have something like O(n) compared to C<em>O(n) = O(c</em>n) = O(n). The complexity of the algorithm and general running time for large values will be about the same on both Computer A and Computer B. </p> <p>If you analyze an algorithm's running time using something like big O notation, then you will have a much better idea about how the algorithm really works. Computer performance won't give you any kind of advantage when you are comparing an algorithm that is O(logn) compared to O(n^2). </p> <p>Take a look at some of the data values for n: </p> <p>I will assume 1 second per operation for the slow computer, and 2 operations for second for the fast computer. I will compare the better algorithm with the slow computer with the worse algorithm with the fast computer.</p> <p><strong>for n = 10:</strong></p> <blockquote> <p>Algorithm 1: O(logn): 4 operations Slow computer: 4 seconds </p> <p>Algorithm 2: O(n^2): 100 operations Fast computer: 50 seconds</p> </blockquote> <p><strong>for n = 100:</strong></p> <blockquote> <p>Algorithm 1: O(logn): 7 operations Slow computer: 7 seconds</p> <p>Algorithm 2: O(n^2): 10,000 operations Fast computer: 1.4 hours</p> </blockquote> <p>Large difference</p> <p><strong>for n = 1,000:</strong></p> <blockquote> <p>Algorithm 1: O(logn): 10 operations Slow computer: 10 seconds</p> <p>Algorithm 2: O(n^2): 1,000,000 operations Fast computer: 5.8 days</p> </blockquote> <p>Huge difference</p> <hr> <p>As n increases, the difference gets bigger and bigger. </p> <p>Now if you tried to run each of these algorithms on a faster/slower computer for a large input size. It wouldn't matter. Hands down the O(logn) would be faster.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload