StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I am curious as to why it is that you want to be able to do this. In my experience when someone says: "I want to ascertain the runtime complexity of this algorithm" they are not asking what they think they are asking. What you are most likely asking is what is the realistic performance of such an algorithm for likely data. Calculating the Big-O of a function is of reasonable utility, but there are so many aspects that can change the "real runtime performance" of an algorithm in real use that nothing beats instrumentation and testing.</p> <p>For example, the following algorithms have the same exact Big-O (wacky pseudocode):</p> <p>example a:</p> <pre><code>huge_two_dimensional_array foo for i = 0, i < foo[i].length, i++ for j = 0; j < foo[j].length, j++ do_something_with foo[i][j] </code></pre> <p>example b:</p> <pre><code>huge_two_dimensional_array foo for j = 0, j < foo[j].length, j++ for i = 0; i < foo[i].length, i++ do_something_with foo[i][j] </code></pre> <p>Again, exactly the same big-O... but one of them uses row ordinality and one of them uses column ordinality. It turns out that due to locality of reference and cache coherency you might have two <em>completely</em> different actual runtimes, especially depending on the actual size of the array foo. This doesn't even begin to touch the actual performance characteristics of how the algorithm behaves if it's part of a piece of software that has some concurrency built in.</p> <p>Not to be a negative nelly but big-O is a tool with a narrow scope. It is of great use if you are deep inside algorithmic analysis or if you are trying to <em>prove</em> something about an algorithm, but if you are doing commercial software development the proof is in the pudding, and you are going to want to have actual performance numbers to make intelligent decisions.</p> <p>Cheers!</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