StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The time complexity is an indicator of the runtime of a function relative to the amount of its input data.</p> <p>given n data items for a function,</p> <ul> <li>O(n) means a function will simply pass over each data item "once". So doubling the input amout will double its duration.</li> <li>O(n<sup>2</sup>) would mean that a function for example has two nested loops over the data, so double the input amount and wait 4 times as long.</li> <li>O(log n) for example would only need logarithmic time, e.g. when you give 10 times more input, the function will only take one "step" longer.</li> <li>O(sqrt(n)) thus means when you give 4 times the input of a call, the function will only take twice the time.</li> </ul> <p>The Big-O-Notation only states how a function scales, but not how long it actually takes. For instance, the Big-O-Notation ignores constant factors. e.g. A function that iterates 4 times over some data (4x loop in sequence) has O(4n), and that is equal to O(n).</p> <p>This fact also shows why O(log<sub>10</sub> n) is equal to O(log<sub>2</sub> n): log<sub>10</sub> n = (log<sub>2</sub> n) / (log<sub>2</sub> 10). As (log<sub>2</sub> 10) is a constant factor, it can be omited in Big-O-Notation. Thus you can choose whatever log you like, it will not mean any difference concerning Big-O-complexity.</p> <p>When you have two inputs, say lists A and B, you use two variables for there size, say n resp. m. A function that has complexity O(n^2 * log m) behaves as follows:</p> <ul> <li>doubling list A will result in much slower execution (i.e. 4x duration) but</li> <li>doubling list B will only result in only "one more iteration" over the A's processing duration of O(n<sup>2</sup>) (i.e. it will only take n^2 * (any unknown constant factor) longer.)</li> </ul>

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