StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Typically, an algorithm's runtime does not include the time required to prepare the data for processing. There's no fundamental reason why it has to be this way, though it is nice because for algorithms that take sublinear time (for example, the O(log n) runtime of binary search), we don't want to account for the amount of work required to prepare and sort the array first.</p> <p>This approach does have several advantages. Imagine that you want to perform some operation many, many times (such as a binary search). If the complexity of binary search included the cost required to prepare and sort the array, then we couldn't get the runtime of "perform k binary searches" by taking the runtime of binary search and multiplying by k. We'd have to take the runtime of binary search, subtract out the work required to prepare the input, multiply that by k, then add back in the one-time cost associated with setting everything up.</p> <p>That said, runtime analysis usually <strong>does</strong> include the amount of time required to generate the <strong>output</strong>. For example, if you have an algorithm that produces a list of n values, it must take at least Ω(n) time because you can't actually write out n values without doing n units of work. This cost is usually accounted for when analyzing the algorithm in the first place. You can sometimes use this fact to show that algorithms with certain runtimes can't exist; for example, there can't be an algortihm that generates the first n powers of two in time less than Ω(n), because you can't write out that many numbers that quickly.</p> <p>The fact that we typically skip the setup time for a problem has its roots way back with Turing machines, where the input was assumed to be written down on the tape before the Turing machine even begins its operation.</p> <p>Hope this helps!</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