Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>EDIT: Quick note, this is almost certainly confusing <a href="http://en.wikipedia.org/wiki/Big_O_notation" rel="noreferrer">Big O notation</a> (which is an upper bound) with Theta notation (which is both an upper and lower bound). In my experience this is actually typical of discussions in non-academic settings. Apologies for any confusion caused.</p> <p>In one sentence: As the size of your job goes up, how much longer does it take to complete it?</p> <p>Obviously that's only using "size" as the input and "time taken" as the output &mdash; the same idea applies if you want to talk about memory usage etc.</p> <p>Here's an example where we have N T-shirts which we want to dry. We'll <em>assume</em> it's incredibly quick to get them in the drying position (i.e. the human interaction is negligible). That's not the case in real life, of course...</p> <ul> <li><p>Using a washing line outside: assuming you have an infinitely large back yard, washing dries in O(1) time. However much you have of it, it'll get the same sun and fresh air, so the size doesn't affect the drying time.</p></li> <li><p>Using a tumble dryer: you put 10 shirts in each load, and then they're done an hour later. (Ignore the actual numbers here &mdash; they're irrelevant.) So drying 50 shirts takes <em>about</em> 5 times as long as drying 10 shirts.</p></li> <li><p>Putting everything in an airing cupboard: If we put everything in one big pile and just let general warmth do it, it will take a long time for the middle shirts to get dry. I wouldn't like to guess at the detail, but I suspect this is at least O(N^2) &mdash; as you increase the wash load, the drying time increases faster.</p></li> </ul> <p>One important aspect of "big O" notation is that it <em>doesn't</em> say which algorithm will be faster for a given size. Take a hashtable (string key, integer value) vs an array of pairs (string, integer). Is it faster to find a key in the hashtable or an element in the array, based on a string? (i.e. for the array, "find the first element where the string part matches the given key.") Hashtables are generally amortised (~= "on average") O(1) &mdash; once they're set up, it should take about the same time to find an entry in a 100 entry table as in a 1,000,000 entry table. Finding an element in an array (based on content rather than index) is linear, i.e. O(N) &mdash; on average, you're going to have to look at half the entries.</p> <p>Does this make a hashtable faster than an array for lookups? Not necessarily. If you've got a very small collection of entries, an array may well be faster &mdash; you may be able to check all the strings in the time that it takes to just calculate the hashcode of the one you're looking at. As the data set grows larger, however, the hashtable will eventually beat the array.</p>
    singulars
    1. This table or related slice is empty.
    1. POWhat is a plain English explanation of "Big O" notation?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJon Skeet
    1. USJon Skeet
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COA hashtable requires an algorithm to run to calculate the index of the actual array ( depending on the implementation ). And an array just have O(1) because it's just an adress. But this has nothing to do with the question, just an observation :)
      singulars
      1. PO
      1. USFilip Ekberg
    2. COjon's explanation has very much todo with the question i think. it's exactly how one could explain it to some mum, and she would eventually understand it i think :) i like the clothes example (in particular the last, where it explains the exponential growth of complexity)
      singulars
      1. PO
      1. USJohannes Schaub - litb
    3. COOh i don't mean the whole answer, just the hashtable lookup and that it can, actually, Never be as fast as a direct adressing :)
      singulars
      1. PO
      1. USFilip Ekberg
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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