Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

26
  • 68
    I would prefer an O(log n) algorithm to an O(1) algorithm if understand the former, but not the latter... Commented Dec 9, 2015 at 13:28
  • 14
    There's tons of impractical data structures with O(1) operations from theoretical computer science. One example would be select() on bitvectors, which can be supported in o(n) extra space and O(1) per operation, using 5 layers of indirection. Simple binary search combined with O(1) rank() turns out to be faster in practice according to the author of the Succinct Data Structure Library Commented Dec 9, 2015 at 13:35
  • 17
    Lower asymptotic complexity does not guarentee faster runtimes. Research matrix multiplication for a concrete example. Commented Dec 9, 2015 at 16:40
  • 56
    Also...any algorithm can be converted to O(1), given a sufficiently large table lookup ;) Commented Dec 9, 2015 at 16:42
  • 20
    @Hoten -- That's assuming the table lookup is O(1), which isn't a given at all for the size of the tables you're talking about! :) Commented Dec 9, 2015 at 22:16