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_algorithmNot 21729 digits, but 2^1729 digits. Practically unusable in any real world case.
https://probablydance.com/2018/05/28/a-new-fast-hash-table-i...
HN submission with related comments: https://news.ycombinator.com/item?id=17177798
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.
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.
I'd proposed a model in a sibling comment that seems to be the one most people use for analyzing algorithms.
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.
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)).
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))
This makes it effective O(1) but worse case O(log n).
If you think about it, a hashtable isn't really that different from a b-tree with a very large value for "b".
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.
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.
If they were zero, the testing would already be done.
Edit: Typo.
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.
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.
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... , 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.”
I tried to make this clear in my comment - (asymptotic) "upper bound" is a concept applicable to any function from N to R. So do you mean the upper bound of the worst case, the upper bound of the average case, the upper bound of the best case, the upper bound of the worst case memory usage, the upper bound of the median price of eggs in China on the nth day since 1970, or something else?
> They are not different functions. They are the same function.
Sure, if you expand the term "function" to include "random variable", which is legitimate to do in some fields of math... but we're talking about deterministic functions from the natural numbers (or real numbers) to the real numbers here. Which is what big-O notation is defined for.
Can you write down the deterministic function from N->R giving the "runtime" of some algorithm? (I mean the actual function, not big-O).
Big-O notation works on mathematical functions. In the usual case, the function you're upper bounding is the worst-case run time of a procedure for a given input size. But that's _far_ from the only case.
The other notations (small o and omega) are about scaling (small o doesn't allow constant factors) and pinching (omega means there are two constant factors, one of which forms a lower bound, and the other an upper bound.
True, the word amortized (i.e. average) is left out here, which still makes people's usage imprecise. But there is a decent argument that amortized is more meaningful than worst-case. Because amortized gives expected throughput and latency, whereas worst-case says very little about throughput and only informs you on the 99th percentile of latency.
> 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.