StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Big O gives the upper bound for time complexity of an algorithm. It is usually used in conjunction with processing data sets (lists) but can be used elsewhere. </p> <p>A few examples of how it's used in C code.</p> <p>Say we have an array of n elements</p> <pre><code>int array[n]; </code></pre> <p>If we wanted to access the first element of the array this would be O(1) since it doesn't matter how big the array is, it always takes the same constant time to get the first item.</p> <pre><code>x = array[0]; </code></pre> <p>If we wanted to find a number in the list:</p> <pre><code>for(int i = 0; i < n; i++){ if(array[i] == numToFind){ return i; } } </code></pre> <p>This would be O(n) since at most we would have to look through the entire list to find our number. The Big-O is still O(n) even though we might find our number the first try and run through the loop once because Big-O describes the upper bound for an algorithm (omega is for lower bound and theta is for tight bound).</p> <p>When we get to nested loops:</p> <pre><code>for(int i = 0; i < n; i++){ for(int j = i; j < n; j++){ array[j] += 2; } } </code></pre> <p>This is O(n^2) since for each pass of the outer loop ( O(n) ) we have to go through the entire list again so the n's multiply leaving us with n squared.</p> <p>This is barely scratching the surface but when you get to analyzing more complex algorithms complex math involving proofs comes into play. Hope this familiarizes you with the basics at least though.</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