Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I think this is a pragmatic approach; O(logN) will never be more than 64. In practice, whenever terms get as 'small' as O(logN), you have to measure to see if the constant factors win out. See also</p> <p><a href="https://stackoverflow.com/questions/1424303/uses-of-ackermann-function/1424397#1424397">Uses of Ackermann function?</a></p> <p>To quote myself from comments on another answer:</p> <blockquote> <p>[Big-Oh] 'Analysis' only matters for factors that are at least O(N). For any smaller factor, big-oh analysis is useless and you must measure.</p> </blockquote> <p>and</p> <blockquote> <p>"With O(logN) your input size does matter." This is the whole point of the question. Of course it matters... <em>in theory</em>. The question the OP asks is, does it matter <em>in practice</em>? I contend that the answer is no, there is not, and never will be, a data set for which logN will grow so fast as to always be beaten a constant-time algorithm. Even for the largest practical dataset imaginable in the lifetimes of our grandchildren, a logN algorithm has a fair chance of beating a constant time algorithm - you must always measure.</p> </blockquote> <p>EDIT</p> <p>A good talk:</p> <p><a href="http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey" rel="nofollow noreferrer">http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey</a></p> <p>about halfway through, Rich discusses Clojure's hash tries, which are clearly O(logN), but the base of the logarithm is large and so the depth of the trie is at most 6 even if it contains 4 billion values. Here "6" is still an O(logN) value, but it is an incredibly small value, and so choosing to discard this awesome data structure because "I really need O(1)" is a foolish thing to do. This emphasizes how most of the other answers to this question are simply <em>wrong</em> from the perspective of the pragmatist who wants their algorithm to "run fast" and "scale well", regardless of what the "theory" says.</p> <p>EDIT</p> <p>See also</p> <p><a href="http://queue.acm.org/detail.cfm?id=1814327" rel="nofollow noreferrer">http://queue.acm.org/detail.cfm?id=1814327</a></p> <p>which says</p> <blockquote> <p>What good is an O(log2(n)) algorithm if those operations cause page faults and slow disk operations? For most relevant datasets an O(n) or even an O(n^2) algorithm, which avoids page faults, will run circles around it.</p> </blockquote> <p>(but go read the article for context).</p>
    singulars
    1. This table or related slice is empty.
    1. POO(log N) == O(1) - Why not?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USBrian
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POO(log N) == O(1) - Why not?
      singulars
      1. PTQuestion
    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. VTDownMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COA clearer restatement of the original question.
      singulars
      1. PO
      1. USNick Johnson
    2. COI find it interesting that you propose a dataset that could potentially take the entirety of our grandchildren's lives to run, and you want to code it both ways (O(1) and O(logN)) and measure the times with test data. You know, instead of being pragmatic about it (like your answer suggests being) and just choosing the one that academically should fair better. If your algorithm is literally costing lives to run, wouldn't you rather have something more than a hunch to fall back on when people question why it didn't finish in time?
      singulars
      1. PO
      1. USmrduclaw
    3. COI apologize if I was unclear, what I meant regarding grandchildren is that maybe today the biggest dataset you'll use is perhaps on the order of 10^9, and I can imagine 50 years from now it might be 10^20, or whatever, but even then my assertion still holds. Even for incredibly huge numbers, logN is still small enough that you can't make practical decisions between logN and 1 based on complexity theory.
      singulars
      1. PO
      1. USBrian
 

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