Hacker News Reader

Comment by michalc | Hacker News Reader

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.

View on HN

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

> 21729 digits

Not 21729 digits, but 2^1729 digits. Practically unusable in any real world case.

Thank you. I should have checked for copy-paste errors, but it's too late to fix it now.

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-i...

HN submission with related comments: https://news.ycombinator.com/item?id=17177798

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

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.

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.

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.

A Turing machine can do constant-time arithmetric (or more simply, constant-time bound arithmetic) for operands of bounded size, as was suggested above.

Same applies to trees thought: you have to multiply log n by that bit number, because each naive comparison will take O(bit number)

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.

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.

>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)).

> 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))

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)

Rehashing can be done incrementally; aside from the additional memory allocation, incremental rehashing can be O(1) rather than O(n).

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).

Java does something similar, decaying its HashMap into a binary tree after enough collisions.

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.

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".

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.

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).

> 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.

Hash tables with buckets are the simplest implementation, but also the least performant. Cuckoo hashing for example deals with collisions differently.

Java switches to Red-Black after a bucket's linked list's length has grown upto some constant number(8?).

Or use probing.

> 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.

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.

The real costs of testing are clearly nonzero.

If they were zero, the testing would already be done.

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.

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.

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).

> 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.

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.

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... , 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.”

Quicksort has O(nlogn) worst case complexity when you use https://en.wikipedia.org/wiki/Median_of_medians just FYI.

When referring to the O() of a particular algorithm without further specification, upper bound is what is meant. When discussing the asymptotics of quicksort you say that it is O(nlog(n)) in the average case, not that it is O(nlog(n)) in general.

> upper bound is what is meant

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?

Ya, I just mean that without further qualification, it's the upper bound of the whole function that's being referred to, which is equivalent to the upper bound of the worst case.

No, you still don't understand. The worst-case runtime and the average-case runtime are different functions. There's no one "whole function" that both are part of.

They are not different functions. They are the same function. The average case is a special case of the general function in which some of the terms collapse.

I don't know what to say at this point. Any reputable reference will disagree with you, including the two Stack Overflow links I posted, or even the Wikipedia article on big-O notation, which doesn't say anywhere that it has to do with the worst case of algorithms.

> 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).

This does not match my experience at all. I have never (including in academia) encountered use of Big O which implicitly referred to the worst case - it has _always_ referred to the average case. That being said, usage has rarely been implicit in my experience - average or worst has almost always been explicitly stated.

You're wrong about this. g in O(f) is defined as: There exists c, m such that for all n > m , c*f(n)>g(n). Big O notation doesn't care about algorithms or worst cases.

No, it doesn't care about worst cases. But the asymptotics of the generalized function of the runtime by necessity are it's worst case.

It is an upper bound on the growth. But _what_ you're upper bounding is not specified.

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.

Big O can b the upper bound can be for the amortized worst case though.

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.

In colloquial usage among programmers "Big-O" almost always really means Big-Theta.

This is true, but it's not related to what we're talking about in this thread.

Reply on news.ycombinator.com