6 ms·

Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n)

Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster, > for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better The Big O notation describes how the number of operations scales as the size of the input tends to infinity: the asymptotic complexity. This means that an O(1) algorithm can include some fixed number of operations, even enough to add _years_ onto the runtime, and still be classed as O(1). Essentially I don’t think it’s really enough to consider the asymptotic complexity of algorithms to compare practical runtimes. You need to know what the smaller-order / constant terms are.

amelius 7y ago
Also, most hash tables are not really O(1). The worst case scenario is more like O(n).
- Darmani 7y ago
  In some senses, no hash tables are O(1). Hash tables are bounded below by the speed of arithmetic. A trillion-bit number takes a while to multiply. You may have never touched a trillion-bit number, but it's called "asymptotic" for a reason. You only get O(1) if you use a model of computation in which arithmetic is constant time. It's simple to work with, even though it's not realistic, and opens up scenarios where you can encode a really complex operation into adding/multiplying some huge numbers, and then claim the overall computation is still fast. Some theorists use a model of computation in which, if your input size n, then multiplying a log-n bit number is O(1), but multiplying an n-bit number is O(n). I have no idea how this is well-defined.
  - lostmsu 7y ago
    Same applies to trees thought: you have to multiply log n by that bit number, because each naive comparison will take O(bit number)
  - dmurray 7y ago
    Constant-time arithmetic is realistic in most normal situations, like evaluating the performance of a hash table implementation. Perhaps your implementation uses 32 bits for the hash function, and can only scale to 4 billion slots. Maybe your implementation of a vector has the same limitation. In general, the reason you'll have trouble trying to store 2^trillion items is not because you chose a data structure with worse asymptotic performance than you expected, it's because you run out of space in the universe in which to store them. So saying such a structure has O(1) asymptotic access time is not perfectly true in a mathematical sense, for unrealistic numbers. But it's certainly realistic.
    - jhanschoo 7y ago
      Yes, it is, but the question is how do you make this notion of "realistic" formal and rigorous. The usual model for complexity analyses, the TM, can't do constant-time arithmetic. So we're interested in a more powerful model. I'd proposed a model in a sibling comment that seems to be the one most people use for analyzing algorithms.
      - johncolanduoni 7y ago
        A Turing machine can do constant-time arithmetric (or more simply, constant-time bound arithmetic) for operands of bounded size, as was suggested above.
  - denormalfloat 7y ago
    That's not what big O notation is about. It represents the growth rate. In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table. Putting a trillion bit integer into a hash table of other integers is still O(1); it's a constant.
    - Kranar 7y ago
      >In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table. But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n)). By the pigeon hole principle, it is impossible to store N items in a hash table using a key whose representation is less than log(N) bits without a collision. This means that there is a relationship between the the size of the key being hashed and the number of elements being inserted in the hash map, specifically the relationship is an element of O(log(n)).
      - davedx 7y ago
        > But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n)) I'm sorry, but as a reader it is quite amusing that various posters are claiming (all without citing any sources) hashtables are O(1), O(n) and O(log(n))
  - jhanschoo 7y ago
    Indeed, in the TM model hash table lookups are necessarily Omega(n) in the length of data stored. The model of computation used in these analyses and interview questions I'd say is a random-access infinite register machine of infinite size (and constant arithmetic), which is more powerful than a TM (and siblings) in complexity analyses. Of course, they are useless for analyzing complexity classes of computational problems, but you can use them to talk about the complexity of computer algorithms.
- Franciscouzo 7y ago
  The general assumption is that the hash function used is a random oracle, if your hash function is H(s) = 0, then you will obviously end up with lots of collisions.
- proverbialbunny 7y ago
  It depends on the hash table. Eg, in the D programming language if there is a collision instead of an array it uses a red-black tree. This makes it effective O(1) but worse case O(log n).
  - denormalfloat 7y ago
    Java does something similar, decaying its HashMap into a binary tree after enough collisions.
- viraptor 7y ago
  People keep skipping a word and a qualifier. The precise description is "hash tables with appropriately chosen growth condition have amortised insert cost of O(1)". The amortised bit effectively hides the occasional rehashing. (It's about throughput, not latency)
  - loeg 7y ago
    Rehashing can be done incrementally; aside from the additional memory allocation, incremental rehashing can be O(1) rather than O(n).
whack 7y ago
> Essentially I don’t think it’s really enough to consider the asymptotic complexity of algorithms to compare practical runtimes. You need to know what the smaller-order / constant terms are. Nitpick: even if you know the constant terms, that would only tell you the number of operations required to execute the code. That's not enough to compare runtimes, because runtimes are also impacted by other factors like branch prediction rate and cache hit rate. You need to consider those factors as well, in order to compare runtimes. At some point, articles become completely unreadable when they try to address every possible nitpick. Some tangents are better left unexplored in a blog post.
- travisjungroth 7y ago
  This is why benchmarking can be useful. I’m not sure why in a field where the materials cost of testing an idea is zero it’s done so much less frequently than theorizing.
  - naniwaduni 7y ago
    The real costs of testing are clearly nonzero. If they were zero, the testing would already be done.
    - travisjungroth 7y ago
      Real costs are certainly more than zero, but it’s almost entirely time. “Materials cost” is what I rounded off to zero. Like if you want to benchmark an idea in aviation, you’re going to have to burn some fuel.
  - jtc331 7y ago
    Maybe because that commits you to a specific implementation with all of its particular choices instead of being able to compare the class of problems and solutions. Edit: Typo.
darawk 7y ago
Also of note, hash tables (unless they are using perfect hashing) are not O(1). Big O notation refers to the worst case time, and the worst case time for a hash table is when the hash key is non-unique and the desired element needs to be looked up in a table. The relation between N and the complexity of this operation is somewhat implementation / data distribution dependent, but in the true worst case it is O(N) (all keys in the same bucket).
- umanwizard 7y ago
  > Big O notation refers to the worst case time Not true. Big O notation can refer to worst case time, average case time, best case time, or any other possible mathematical function from integers or real numbers to real numbers. Big-O notation is in fact independent of computer science. It’s sometimes taught in calculus courses and used to describe arbitrary functions that have nothing to do with algorithm running times.
  - mercutio2 7y ago
    Big-O in Bachmann–Landau notation specifically means the upper bound. There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things. But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precisely, is anything but upper bound.
    - umanwizard 7y ago
      Yes. The upper bound of some function. That function is not necessarily the worst-case runtime. Best-case, average-case, and worst-case can all have upper bounds. If the best case runtime as a function of data size is n/2, average case is n^2 + 5x, and worst case is e^n + 5n^2, these functions are asymptotically upper bounded by n, 2n^2, and 2e^n respectively, so they are big-O (incidentally they are also big-Omega and big-Theta) of n, n^2, and e^n respectively. Big-O means the same thing in CS as it does in mathematics; this is not an issue of different domains using terms in different ways. See for example: https://stackoverflow.com/questions/42144251/why-is-big-oh-o-also-used-to-represent-average-case-and-best-case-in-an-algori https://stackoverflow.com/questions/42144251/why-is-big-oh-o... , https://stackoverflow.com/questions/3905355/meaning-of-average-complexity-when-using-big-o-notation https://stackoverflow.com/questions/3905355/meaning-of-avera... A famous example is Quicksort which is O(n*log(n)) average case, but not worst case where the tightest big-O bound is O(n^2). Any reputable reference you look up will agree with this. From Wikipedia, for example: “Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.”
deleted 7y ago
[deleted]
gruez 7y ago
Another question: doesn't the O(1) property of hashtables require that there's no collisions? Because of the birthday paradox, you'll need an insanely large hashtable to avoid collisions, and if you don't (or get unlucky), the performance approaches O(n) as the hashtable gets fuller. If you think about it, a hashtable isn't really that different from a b-tree with a very large value for "b".
- cellar_door 7y ago
  Collisions are expected (fill factors are typically typically 2/3 to 3/4). You make every bucket in the table a linked list. And check each value in the list against that for which you are searching.
  - dplavery92 7y ago
    This, I believe, is the exactly the behavior the parent commenting was describing (and bemoaning.) If you you have to check against every term in a linked list (an operation proportional to the length of the list), then your hash table ceases to be constant-time once you get collisions. In that case, if you have a hash table of fixed size, but arbitrarily increase the number of entries in the table, then the look-up time tends as O(n).
    - avl999 7y ago
      > if you have a hash table of fixed size No HashTable implementation worth it's salt is going to have a fixed size table. They are going to dynamically grow the size of the table (double it) once certain level of utilization is reached in the table (say 50%). In practice this means that chains at the same bucket will be of some small constant length assuming a good hash function.
  - adrianN 7y ago
    Hash tables with buckets are the simplest implementation, but also the least performant. Cuckoo hashing for example deals with collisions differently.
  - 7y ago
fyp 7y ago
Looking at the performance graphs of different hash table implementations is the best way to invalidate the idea of "constant time": https://probablydance.com/2018/05/28/a-new-fast-hash-table-in-response-to-googles-new-fast-hash-table/ https://probablydance.com/2018/05/28/a-new-fast-hash-table-i... HN submission with related comments: https://news.ycombinator.com/item?id=17177798 https://news.ycombinator.com/item?id=17177798
lokedhs 7y ago
My favourite example of galactic algorithms is the most efficient way to multiply two numbers. As the Wikipedia page[1] states: An example of a galactic algorithm is the fastest known way to multiply two numbers,[2] which is based on a 1729-dimensional Fourier transform. This means it will not reach its stated efficiency until the numbers have at least 21729 digits [1] https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm
- babuskov 7y ago
  > 21729 digits Not 21729 digits, but 2^1729 digits. Practically unusable in any real world case.
  - lokedhs 7y ago
    Thank you. I should have checked for copy-paste errors, but it's too late to fix it now.
- deleted 7y ago
  [deleted]

amelius 7y ago

Also, most hash tables are not really O(1). The worst case scenario is more like O(n).

Darmani 7y ago
In some senses, no hash tables are O(1). Hash tables are bounded below by the speed of arithmetic. A trillion-bit number takes a while to multiply. You may have never touched a trillion-bit number, but it's called "asymptotic" for a reason. You only get O(1) if you use a model of computation in which arithmetic is constant time. It's simple to work with, even though it's not realistic, and opens up scenarios where you can encode a really complex operation into adding/multiplying some huge numbers, and then claim the overall computation is still fast. Some theorists use a model of computation in which, if your input size n, then multiplying a log-n bit number is O(1), but multiplying an n-bit number is O(n). I have no idea how this is well-defined.
- lostmsu 7y ago
  Same applies to trees thought: you have to multiply log n by that bit number, because each naive comparison will take O(bit number)
- dmurray 7y ago
  Constant-time arithmetic is realistic in most normal situations, like evaluating the performance of a hash table implementation. Perhaps your implementation uses 32 bits for the hash function, and can only scale to 4 billion slots. Maybe your implementation of a vector has the same limitation. In general, the reason you'll have trouble trying to store 2^trillion items is not because you chose a data structure with worse asymptotic performance than you expected, it's because you run out of space in the universe in which to store them. So saying such a structure has O(1) asymptotic access time is not perfectly true in a mathematical sense, for unrealistic numbers. But it's certainly realistic.
  - jhanschoo 7y ago
    Yes, it is, but the question is how do you make this notion of "realistic" formal and rigorous. The usual model for complexity analyses, the TM, can't do constant-time arithmetic. So we're interested in a more powerful model. I'd proposed a model in a sibling comment that seems to be the one most people use for analyzing algorithms.
    - johncolanduoni 7y ago
      A Turing machine can do constant-time arithmetric (or more simply, constant-time bound arithmetic) for operands of bounded size, as was suggested above.
- denormalfloat 7y ago
  That's not what big O notation is about. It represents the growth rate. In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table. Putting a trillion bit integer into a hash table of other integers is still O(1); it's a constant.
  - Kranar 7y ago
    >In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table. But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n)). By the pigeon hole principle, it is impossible to store N items in a hash table using a key whose representation is less than log(N) bits without a collision. This means that there is a relationship between the the size of the key being hashed and the number of elements being inserted in the hash map, specifically the relationship is an element of O(log(n)).
    - davedx 7y ago
      > But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n)) I'm sorry, but as a reader it is quite amusing that various posters are claiming (all without citing any sources) hashtables are O(1), O(n) and O(log(n))
- jhanschoo 7y ago
  Indeed, in the TM model hash table lookups are necessarily Omega(n) in the length of data stored. The model of computation used in these analyses and interview questions I'd say is a random-access infinite register machine of infinite size (and constant arithmetic), which is more powerful than a TM (and siblings) in complexity analyses. Of course, they are useless for analyzing complexity classes of computational problems, but you can use them to talk about the complexity of computer algorithms.
Franciscouzo 7y ago
The general assumption is that the hash function used is a random oracle, if your hash function is H(s) = 0, then you will obviously end up with lots of collisions.
proverbialbunny 7y ago
It depends on the hash table. Eg, in the D programming language if there is a collision instead of an array it uses a red-black tree. This makes it effective O(1) but worse case O(log n).
- denormalfloat 7y ago
  Java does something similar, decaying its HashMap into a binary tree after enough collisions.
viraptor 7y ago
People keep skipping a word and a qualifier. The precise description is "hash tables with appropriately chosen growth condition have amortised insert cost of O(1)". The amortised bit effectively hides the occasional rehashing. (It's about throughput, not latency)
- loeg 7y ago
  Rehashing can be done incrementally; aside from the additional memory allocation, incremental rehashing can be O(1) rather than O(n).

whack 7y ago

> Essentially I don’t think it’s really enough to consider the asymptotic complexity of algorithms to compare practical runtimes. You need to know what the smaller-order / constant terms are. Nitpick: even if you know the constant terms, that would only tell you the number of operations required to execute the code. That's not enough to compare runtimes, because runtimes are also impacted by other factors like branch prediction rate and cache hit rate. You need to consider those factors as well, in order to compare runtimes. At some point, articles become completely unreadable when they try to address every possible nitpick. Some tangents are better left unexplored in a blog post.

travisjungroth 7y ago
This is why benchmarking can be useful. I’m not sure why in a field where the materials cost of testing an idea is zero it’s done so much less frequently than theorizing.
- naniwaduni 7y ago
  The real costs of testing are clearly nonzero. If they were zero, the testing would already be done.
  - travisjungroth 7y ago
    Real costs are certainly more than zero, but it’s almost entirely time. “Materials cost” is what I rounded off to zero. Like if you want to benchmark an idea in aviation, you’re going to have to burn some fuel.
- jtc331 7y ago
  Maybe because that commits you to a specific implementation with all of its particular choices instead of being able to compare the class of problems and solutions. Edit: Typo.

darawk 7y ago

Also of note, hash tables (unless they are using perfect hashing) are not O(1). Big O notation refers to the worst case time, and the worst case time for a hash table is when the hash key is non-unique and the desired element needs to be looked up in a table. The relation between N and the complexity of this operation is somewhat implementation / data distribution dependent, but in the true worst case it is O(N) (all keys in the same bucket).

umanwizard 7y ago
> Big O notation refers to the worst case time Not true. Big O notation can refer to worst case time, average case time, best case time, or any other possible mathematical function from integers or real numbers to real numbers. Big-O notation is in fact independent of computer science. It’s sometimes taught in calculus courses and used to describe arbitrary functions that have nothing to do with algorithm running times.
- mercutio2 7y ago
  Big-O in Bachmann–Landau notation specifically means the upper bound. There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things. But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precisely, is anything but upper bound.
  - umanwizard 7y ago
    Yes. The upper bound of some function. That function is not necessarily the worst-case runtime. Best-case, average-case, and worst-case can all have upper bounds. If the best case runtime as a function of data size is n/2, average case is n^2 + 5x, and worst case is e^n + 5n^2, these functions are asymptotically upper bounded by n, 2n^2, and 2e^n respectively, so they are big-O (incidentally they are also big-Omega and big-Theta) of n, n^2, and e^n respectively. Big-O means the same thing in CS as it does in mathematics; this is not an issue of different domains using terms in different ways. See for example: https://stackoverflow.com/questions/42144251/why-is-big-oh-o-also-used-to-represent-average-case-and-best-case-in-an-algori https://stackoverflow.com/questions/42144251/why-is-big-oh-o... , https://stackoverflow.com/questions/3905355/meaning-of-average-complexity-when-using-big-o-notation https://stackoverflow.com/questions/3905355/meaning-of-avera... A famous example is Quicksort which is O(n*log(n)) average case, but not worst case where the tightest big-O bound is O(n^2). Any reputable reference you look up will agree with this. From Wikipedia, for example: “Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.”

deleted 7y ago

[deleted]

gruez 7y ago

Another question: doesn't the O(1) property of hashtables require that there's no collisions? Because of the birthday paradox, you'll need an insanely large hashtable to avoid collisions, and if you don't (or get unlucky), the performance approaches O(n) as the hashtable gets fuller. If you think about it, a hashtable isn't really that different from a b-tree with a very large value for "b".

cellar_door 7y ago
Collisions are expected (fill factors are typically typically 2/3 to 3/4). You make every bucket in the table a linked list. And check each value in the list against that for which you are searching.
- dplavery92 7y ago
  This, I believe, is the exactly the behavior the parent commenting was describing (and bemoaning.) If you you have to check against every term in a linked list (an operation proportional to the length of the list), then your hash table ceases to be constant-time once you get collisions. In that case, if you have a hash table of fixed size, but arbitrarily increase the number of entries in the table, then the look-up time tends as O(n).
  - avl999 7y ago
    > if you have a hash table of fixed size No HashTable implementation worth it's salt is going to have a fixed size table. They are going to dynamically grow the size of the table (double it) once certain level of utilization is reached in the table (say 50%). In practice this means that chains at the same bucket will be of some small constant length assuming a good hash function.
- adrianN 7y ago
  Hash tables with buckets are the simplest implementation, but also the least performant. Cuckoo hashing for example deals with collisions differently.
- 7y ago

fyp 7y ago

Looking at the performance graphs of different hash table implementations is the best way to invalidate the idea of "constant time": https://probablydance.com/2018/05/28/a-new-fast-hash-table-in-response-to-googles-new-fast-hash-table/ https://probablydance.com/2018/05/28/a-new-fast-hash-table-i... HN submission with related comments: https://news.ycombinator.com/item?id=17177798 https://news.ycombinator.com/item?id=17177798

lokedhs 7y ago

My favourite example of galactic algorithms is the most efficient way to multiply two numbers. As the Wikipedia page[1] states: An example of a galactic algorithm is the fastest known way to multiply two numbers,[2] which is based on a 1729-dimensional Fourier transform. This means it will not reach its stated efficiency until the numbers have at least 21729 digits [1] https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm

babuskov 7y ago
> 21729 digits Not 21729 digits, but 2^1729 digits. Practically unusable in any real world case.
- lokedhs 7y ago
  Thank you. I should have checked for copy-paste errors, but it's too late to fix it now.
deleted 7y ago
[deleted]