Big O, Little N | Hacker News Reader

Big O, Little N

adamzerner.bearblog.dev

81 pointsadamzerner139 comments

> const isVowel = (char) => ["a", "e", "i", "o", "u"].includes(char);

> [... ] it hit me that it's actually O(n), because we've got an array and have to iterate over every element to see if the element matches char.

This depends on how you define your `n`. Usually this would be defined as the input size. Unless you would like to be able to run this on arbitrary definitions of what a "vowel" is (and in this case, it's indeed both small and static), the only useful interpretation would be to consider this function O(1), regardless of iteration over this 5-element list. If the list of vowels would considered a parameter, it would indeed be O(n) or O(m).

You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)! :)

Depends. Are we talking about people who know what O(n) means? Parent comment explained it very well - "n" is typically your input size (or if it's not, you need to clearly define what it is). "n" is unlikely to ever be "number of vowels in the English alphabet" because that's a constant, that doesn't change at all when input changes.

O(n) is meaningless if we don't say anything about "n", so no, 'iterating an array" is not necessarily O(n) - it's only so when the array has a size proportional with the input.

Or, to put it differently: yes "array.includes" is not O(1) in common discussions, because typically we discuss the complexity of method `includes` as relative to the size of the array; but a program/algorithm that contains an invocation of `array.includes` does not automatically have complexity that is linear or worse - it can very well be logarithmic or constant. For example, looking up a value in a hashtable where the keys are strings is considered to be constant time, even though you need to iterate over the key in order to obtain its hashcode (i.e. the algorithm that takes a string and produces a hashcode is O(n) where n is the length of the string).

This only makes sense if you consider a `contains` method to only take the arguments passed inside of the parenthesis. But in actuality there is an implicit `this` argument too. Armed with this knowledge it becomes trivial to see how the total input to the function is `N + 1` values. `N` being the length of the function, and the `1` representing the thing we're searching for. Since constant values in complexity theory are handily ignored we get an input of size `N`.

And as to your second point, the choice of what is and isn't a constant-time operation is generally a practical concession. There's no reason to say "you can't say anything about any algorithm because it's an implementation detail" here. The conversation is specifically about element presence in an unsorted array. A very simple, easily understood, and unambiguous algorithm. Bringing up the runtime of the operation in a hashtable or in tree-structures is entirely nonsensical and just destroys any conversation there is to be had.

Are you saying that because (JavaScript!) functions have a "length" property representing number of arguments, they are all O(N) (or greater)? (btw I don't see how "this" fits in here.)

The only way I can see it making sense is because a function could take arbitrarily many arguments. Why on earth would that matter if the function doesn't do anything with those arbitrarily many arguments? We may not know in advance what a caller gives to a function, but of course we know what the function does with its arguments--it's a function's body that we're analyzing and classifying a Big-O for!

Another way to look at it: If A is a constant array and part of the program - and not an input, A.includes(x) is just a shorthand for a switch-case statement.

array.includes(x) is really a function includes(array, x), and this is O(n,1).

I've never seen Landau's notation with two variables, I don't think it exists. At best you could say it is O(n)*O(1) which is formally equivalent to O(n).

You can easily extend Landau's notation to multiple variables (or rather functions of multiple arguments). It's even pretty commonly done, eg a common statement is something like "Getting the k largest elements out of an unsorted input of n elements, takes O(k log n) time, if you use a heap."

> At best you could say it is O(n)*O(1) which is formally equivalent to O(n).

Sorry, that's not how you would use or define multi-variable Big-O notation, if you want it to make any sense.

See eg https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variab... for more details.

>You can easily extend Landau's notation to multiple variables [...] O(k log n)

Yes, but the parent wrote O(n, 1) not O(n * 1). Does O(k, log n) exists?

> Sorry, that's not how you would use or define multi-variable Big-O notation, if you want it to make any sense.

What do you mean? If I have f: n -> n and g: n -> 1, can I not say O(f) * O(g) = O(f*g) ? See https://math.stackexchange.com/a/2317054 for an example of demonstration.

First, the usual way of just writing O(1) or O(n) or O(n^2) is kind of an abuse of notation.

Big-O is a mapping from a function, like O(n -> 1) or (n -> n) or (n -> n^2) or (x -> sin x) to a set of functions.

Function don't care about renaming of arguments. (n -> 2 n) is the same function as (x -> 2 x).

When you write O(k log n) what you really mean is O((k, n) -> k log n)

And you can indeed take it apart:

O((k, n) -> k) * O((k, n) -> log n) == O((k, n) -> n log n)

(For some suitable definition of what multiplication of sets of functions means.)

That's very different from functions with single arguments like in your example.

(And, yes, your example works. It's just a different thing.)

Linear search is O(n), but here, n is 5, and O(5) is O(1).

array.includes() is an O(n) method in the size of the array.

isVowel(c) implemented using array.includes() on a fixed size array is O(1) operation - it does not depend on the size of its input.

You can see this more clearly by asking what complexity does array.all(isVowel) have? Well, for each character in array, it needs to do 5 comparisons. So, for n characters it will do 5 * n operations. So, it is in O(n). This also proves that isVowel() is an O(1) operation.

Now, if we were to think about comparing to all vowels in all languages, you can also say that isVowel() is O(n) complexity in the number of vowels. The above analysis would show that array.all(isVowel) is O(n * m), with n being the number of characters in array and m being the number of vowels we are considering. Even this though is pretty strange, since Big O complexity analysis is only relevant if you are interested in the growth of n and m, which is unlikely for the number of vowels.

> You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)!

In general, it is O(N). In this example, it is O(1). When your N is fixed (or even upper bounded), then it is always O(1). This is standard in how it is taught, and I've even said O(1) in interviews where I had a nested for loop, because the size of the iteration was fixed in both loops. The interviewer agreed with me.

Heck, I did this even in an interview where N could be arbitrarily large, but I argued that for the problem domain, it is extremely unlikely that N would be bigger than some amount - here N represented the number of direct reports a manager has. I said that in theory it was O(N), but in practice (or on average), it would be O(1). Again, the interviewer accepted the answer.

Yeah I was working on an elevator control problem and made mention about how this doesn't have great time complexity, but the number of floors is surely less than 163.

> When your N is fixed (or even upper bounded), then it is always O(1).

I had to read this sentence over several times. I... think you've just filled in a missing piece of my college CompSci education.

Previously, I never really understand why we measured algorithms this way, beyond "it's a rough classification and nothing is perfect." What I didn't quite realize until just now is, this classification assumes N is a variable that could be any value in the universe—and so you have to optimize for that eventuality.

If N is known, the iterations don't matter—because of course they don't.

(Disclaimer: I've been out of college for a while and I don't use algorithms in my daily life, it's possible I just forgot this. Or that I'm making a fool of myself right now!)

You sound like my teacher.

This is pedantic, you are purposely using an unreasonable interpretation of "it's actually O(n)".

Any function taking just a char would be O(1) since it only has 256 values n can take, discussing their complexity would be meaningless making it obvious that someone talking about the complexity of includes() is talking about the size of the array.

The goal of computer science is to get insight about the performance of programs, not being pedantic and reduce the problem to the absurd that have an obvious answer, in this context the meaning of O(n) is perfectly clear.

I disagree, precisely because of your last sentence. The only meaningful interpretation of the proposed `isVowel` function is O(1), unless you want to accommodate arbitrary definitions of what characters are considered vowels.

Remember that O() is concerned with asymptotic behaviour as the input grows - for a constant set of vowels to check against, the running time does not grow and the function is therefore O(1).

An O(n) function can absolutely be part of an O(1) function.

To the authors point, Big-O describes asymptotic growth and for small values of n, O(n^2) may perform better than an O(1) function. You also need a definition for `n`. What would you define as `n` for the `isVowel` function?

Yes, isVowel regardless of its implementation has all its input of fixed size, both the array and the one element to look for.

In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever?

Maybe we should only talk about properly defined algorithms whose inputs have been formally defined, but since we are talking complexity, I assumed something will grow.

It is either the array, or `char`. The set of vowels is finished for a given language but its size can change between languages and `char` will always be less than 256 (or some other fixed value).

Since isVowel is a closure it's not crazy to consider the array as part of the input.

You say "the only useful interpretation would be to consider this function O(1)" but it is possible to read this as an example and that n relates to the size of the array and in that case saying it is O(n) makes sense.

Since this is not a formal discussion of complexity and n has not been defined, I think it's fairer to interpret the post in a way where it makes sense .

> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever?

Yes, because there is no "n" involved. For example, this code:

  for i in 1...1_000_000 {
      print(i)
  }
  return ["a", "e", "i", "o", "u"].contains(character)

is still O(1), it just has a higher constant factor. The only exception is that you could have psuedo-polynomial algorithms that depend on the value input itself, like

  func foo(i: Int) {
      for _  in 1...i {
          print(i)
      }
  }

> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever?

Yes.

Your statement about char I disagree with. A char is a byte, as you say. But that means it has numerical value as well. I could have a "identityMatrix" function that takes a char (because I decide I won't have matrices with a dimension > 256); it would be O(n^2) in operation though. In fact, I could have a 3 dimensional identity matrix creation function, and then it would be O(n^3). I could have a brute force generation of all possible permutations of the numbers 0-input, and now it's O(256!). The input of the function does not tell you anything about the complexity of the function (though it may tell you the max value of N. But, for instance, a function of O(n!) is almost assuredly going to be far, far worse than one with O(1), even if the size of N is maximally 256).

All that aside, I agree that the OP is O(1). It does 5 comparisons. It always does 5 comparisons, regardless of the input of the isVowel function. Yes, includes, evaluated out of context, is O(n), but you know something about the context it's used in to be able to give isVowel a tighter bound. That's usually what the goal of Big O is; not to define ~a~ bound, but define the most conservative.

Computational complexity theory is all about being very pedantic, and GP's conclusion is spot on.

Yep O(5) = O(1)

Author here. Yeah that makes sense. I didn't realize it at the time.

However, I think the example still demonstrates the larger point that I was making. `.includes` takes linear time proportional to the array that calls it, but the fact that it's linear time isn't a bad thing because the size of the array is five.

A linear time algorithm ('.includes') is a constant time algorithm when its input is constant. Of course, the other input to '.includes' (the char) can vary in value, but to know if that affects running time we'd have to look at the implementation of '.includes'.

I'm not sure what you mean, how can it be constant? You have to check each element in the array and there are n elements in the array.

If you define `n` as "the number of vowels in the input language", making it dynamic, then yes.

However, the list of vowels in the function is static. So the execution time doe snot grow as the input size grows (there is only a single char as input).

O(5) = O(1) = constant.

.includes() is O(n), though.

Sounds like you might need a refresher (it's easy to get fuzzy over the years, happens to the best of us).

But you may want to update the blog post as not to confuse others more, I think people have exams coming up ;)

Yeah, I have learned a few things from the comments here and my understanding isn't perfect. Previously I thought of `n` as arbitrary; that it can be whatever you define it to be. I see now that you're right that technically it has a more precise definition: it refers to the input size.

However, I also think that in _practice_, as Znafon [says](https://news.ycombinator.com/item?id=24661411), the meaning of `n` is clear and it makes sense to stretch the technical definition a bit. In my experience, people often do. Imagine if there were one trillion vowels. It wouldn't be practical to describe it as an O(1) algorithm, despite what the answers to exam questions might say.

That said, I think that it is worth understanding the distinction between what `n` means in theory vs practice, so I was going to add a note to the blog post in order to avoid confusing readers, like you recommend. However, as I tried to do so, things got too side-tracked. Too many tangents, especially ones that aren't the easiest to understand, makes the post harder to follow. So I decided on linking to this thread parenthetically. That seems to my eye to strike the right balance.

Of course if you are looking to see whether a lower-case letter is one of a set, you use a bitmap:

  bool isvowel(char c){ return (1<<c-'a')&0x104111; }

Often O(1) is better than O(n) even for small n.

Often O(1) is better than O(1).

Modern compilers will turn

  bool isvowel(char c){
    switch(c){
    case'a':case'e':case'i':case'o':case'u': 
      return true;
    }
    return false;
  }

into sort-of the same code (after a range check). https://godbolt.org/z/aMcdY6

Looking at the code actually produced, the compiler has noticed that all the vowels are even-numbered characters (0,4,8,14,20), so combined the range check with a "rotate-right" so it can compress 0x104111 down to 0x495, and shift that right and check the low bit of the result instead of doing a "bt", or bit-test. It's anybody's guess why that is considered better; shifts are supposed to be constant-time; but checking the low bit is a byte-sized operation. So, maybe

  bool isvowel(char c){ return (0x104111>>c-'a')&1; }

is better: https://godbolt.org/z/M784cK

> So, maybe [...] is better

You were one click away of using LLVM's Machine Code Analyzer (MCA) within godbolt to see why one of the two isvowel one-liners is objectively better than the other: https://godbolt.org/z/fGEv3c

This version:

bool isvowel(char c){ return (0x104111>>c-'a')&1; }

puts way more pressure on Port 2 on skylake, reducing the number of IPC that can be scheduled. The first version is therefore a bit better.

;)

Today I learned six new things:

  - Clang thinks compressing 0x104111 to 0x495 is a good idea
  - Clang thinks 0x495>>((c-'a')>>1)&1 is better than
      1<<c-'a'&0x104111
  - LLVM has a machine code analyzer
  - Godbolt has a button to apply it
  - Clang is wrong about that
  - Gcc-9 and newer prefers to index into a jump table, 
      instead of bitmasking. (!)

Yet another reason to set up a periodic contribution to Godbolt.

While deprecated, intel has also an opensource machine code analyzer called IACA.

It is also worth pointing out that these "analyzers" are just tools that simulate particular CPU architectures. Their models are just approximations and aren't perfect, so don't take them as a source of truth.

Since the shift count is implicitly modulo 32, you don't even need the subtraction:

    bool isvowel(char c) {
        return (1u << (c&31)) & 0x208222;
    }

The result is unspecified, if you don't mask off the high bits. Some chips will do it implicitly, and give you the right answer anyway, unportably.

This is why testing is not a substitute for correctness. Sometimes you get the right answer by accident.

But it's good enough for code golf.

No, the author didn't really understand how hash tables* work and what the big-O notation really means.

If you do a worst-case analysis, hash tables just degenerate to a single linked list (everything gets hashed to the same bucket), and you don't gain anything by using them. That's where you have 0(n) performance.

But hash tables are probabilistic data structures, so we don't actually look at worst-case performance, but at the average case. It's important that for this analysis we need to make some assumptions about the hash function itself (e.g. what its collision probability is). Out of that, we can compute that hash table operations are on average constant.

* There are actually multiple ways to deal with collisions in hash table, let's focus on open hashing/seperate chaining for now.

You also misunderstand hash tables.. they are not merely expected constant time, they are amortized constant time.

as far as I understand, the amortization factor comes in because you occasionally might have to grow your table of buckets, in the same way that arbitrary-size array lookup is not actually constant, but only amortised constant.

if we sidestep that issue for one moment, it's still true that you have worst case O(n) and average O(1), though.

> arbitrary-size array lookup is not actually constant, but only amortised constant.

Array lookup operations are constant time. You don't need to grow an array while reading from it. Append operations in a vector are O(n) but amortized constant time.

Hash tables work the same way - they have amortized constant time when inserting, but they should have constant time for reads when using a good hash function.

That said, technically we still classify hash table reads and writes as O(n). Big-O notation defines an upper bound on time, not the average time. And the upper bound on hash table reads and writes is O(n) if you have a terrible hash function (or carefully crafted inputs).

This is not useful knowledge though, because hash tables are usually fast in practice. If you're trying to figure out how something performs in practice (like the "isVowel" function in the blog post), the tool to reach for is a benchmark. Guess how a benchmark result will come out before you see the result, and over time you'll build an intuition for these things.

You're right about the lookup being constant and insertions not, I didn't think it through well enough before posting. :)

But I disagree about the O notation. The O notation is just a mathematical notation, it defines certain classes of functions. It can be used for many different things, worst-case complexity is one, but not the only one. It's perfectly possible (and quite common) to describe expected complexity (which is a mathematical function of the input size, too) with O notation.

People do look at expected complexity for probabilistic algorithms and data structures and they are useful. The idea that "O notation is not useful and you should perform benchmarks" should also be taken with a grain of salt, you don't always have time to perform benchmarks (and for good benchmarks, you also have to make some assumptions about the data, in particular when it comes to probabilistic data structures), while you can just read up on O notation for common algorithms (and do a quick in-your-head calculation for custom algorithms, e.g. three nested loops, then it's probably O(n^3), not always of course) and use that at least as a very useful first-order approximation.

But you're right that it's more complex: one of the best examples of this is that the simplex algorithm for linear optimisation is not known to be polynomial (in fact, I think for every possible variant of the algorithm that has so far been proposed, we know that it can degenerate to exponential time with bad inputs), but somehow that doesn't appear to be an issue in practice - it is my understanding that nobody fully understands why not. There are proven polynomial algorithms for linear optimisation, but they are more complicated and therefore less often used.

I think they have recently found polynomial simplex algorithms.

Or I think at least a randomised simplex that has expected polynomial runtime even on the worst case input.

This is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.

I just searched for 'polynomial time simp lex algorithm' and found things like eg https://cstheory.stackexchange.com/questions/2373/complexity... which references https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc....

thanks, it seems to be quite complex though, as far as I understand it's still "only" an expected polynomial algorithm given some assumptions about the input, and not a truly worst-case polynomial algorithm - as opposed to e.g. the ellipsoid method which is actually worst-case polynomial.

As far as I understand it's runs in expected polynomial time regardless of input.

No assumptions on the input necessary.

The expectation is over the choice of random bits created while running the algorithm.

I agree its misleading. Another example is that despite being O(log n), B-trees or skip lists can be much faster than hash tables if your keys are naturally ordered (and queried in order) because of memory caching.

> It's perfectly possible (and quite common) to describe expected complexity (which is a mathematical function of the input size, too) with O notation.

Yep - its common in practice but sloppy. Technically its not big-O anymore if you're doing that. Its big-theta notation. (Same thing, just T(n) instead of O(n)).

https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...

Why is it sloppy? The question of whether you use O or Theta is just that the one gives an upper bound only, and the other one ensures a tight bound (usually many people write O, when they mean Theta, which is not wrong, but is also doesn't tell you as much; in the end, it's mostly clear what is intended though).

That doesn't mean that you can't use either notation to refer to a worst-case or an average-case (given a suitably defined probability distribution) performance. To say "expected complexity for hash table lookup is O(1)" is neither wrong, nor sloppy.

No, they are not amotrized constant time because there is some predefined sequence of inputs that makes them always work in linear time

Though you should be able to sidestep this by doing something like seeding your hash with your hashtable pointer. Then you'd also need control over the memory allocator to break the hashtable.

Nope. Big-O is a mathematical measure, not a practical measure. Mathematically speaking we don't care if malicious input difficult to construct. We care that its possible - which it is - so the upper bound on time is at least O(n).

If you think this isn't useful in practice, you're right! If you want to compare the actual speed of an algorithm, benchmark it. And once you've done enough of that, your intuition will guide you far better than big-O notation ever could.

Randomised algorithms add an interesting wrinkle.

Eg even the worst case input for a randomised QuickSort still has an expected runtime of O(n log n). (Where the expectation is averaged over the random choices, not over the input.)

> Eg even the worst case input for a randomised QuickSort still has an expected runtime of O(n log n).

This statement is imprecise. What is "worst case input" when speaking of "expected".

Mathematically, worst case doesn't mean a known worst case that works every time. As long as I have an input that the random algorithm has a chance of generating the worst case, it will be O(n^2).

From an adversarial standpoint: If I have information about the random algorithm and the seed, I can make exploit it.

So yes, even the randomized Quick Sort has worst case of O(n^2)

> From an adversarial standpoint: If I have information about the random algorithm and the seed, I can make exploit it.

Randomised QuickSort as an algorithm doesn't have any random seed. It just uses pure randomness. (Specific implementations might use a pseudo-RNG.)

> This statement is imprecise. What is "worst case input" when speaking of "expected".

Oh, just the opposite! Speaking of 'expected' tells you exactly what worst-case to look for.

What I mean is that 'worst case input' by itself is not a-priori well-defined for randomised algorithms. Because you could eg have an input that worsens the 75%-ile runtime but improves the 25%-ile runtime.

By specifying eg 'expected', you make clear that you are talking about the worst case for the expected runtime.

> So yes, even the randomized Quick Sort has worst case of O(n^2)

The worst case over both input and random choices is O(n^2). The worst case over input for the expected running time is O(n log n).

Even more, for any input, even the worst case input, randomised quicksort has O(n log n) running time with 'very high probability', ie for any epsilon there's a big enough m and a constant c, so that with probability at least 1-epsilon, the running time of the worst case input of size n > m is smaller than c * n log n.

---

There's a different, but equivalent, way to analyse randomised algorithms that might be easier to digest for you, because it completely avoids having to directly talk about randomness:

Take your favourite deterministic machine model, say a Turing machine or a random access machine, and in addition to the normal input tape, give it access to an extra immutable one-sided 'random' tape that's pre-filled with binary symbols (0 or 1).

Everything is deterministic in this model.

An analysis of the expected runtime for the worst case input means that the adversary gets to prepare the input tape, but for the rest of the analysis we are analysing all possible contents of the 'random tape'.

For each possibility, there is one specific deterministic run. Talking about the expected (worst-case input) runtime just means that we are averaging over all possible 'random' tapes.

If we talk about the 95%-ile instead, that means that we are ordering all the runtimes for the different possibilities for the 'random tape' and taking the runtime of the 95%-ile. Still, everything is deterministic.

When you want to run this algorithm in practice, you sample from the space of possible contents of the 'random tape'. But crucially, the standard assumption is that you sample after your adversary has selected their input.

That standard assumption is in line with Kerckhoffs's principle in cryptography that the adversary knows your system, but that you are able to pick secret random keys at will.

https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle

> seeding your hash with your hashtable pointer

This is not how worst-case complexity analysis works. Worst-case means worst-case, ie. the input is selected by an adversary with complete knowledge of your algorithm and initial memory; and there is no source of randomness other than the input itself.

And, yes, that's usually not applicable in practice. But worst-case complexity is a theoretical concept defined only on abstract machines (implicitly a Von Neumann-like machine here).

Instead, to do useful analysis on hash tables, you should use probability complexity analysis, which allows your algorithm access to a source of randomness the adversary doesn't have access to.

You can analysis the worst-case input, but still average over random choices your algorithm makes.

That gives you 'worst-case expected runtime'. That concept is useful for eg analysing QuickSort with randomised pivots.

You can also analysis worst-case input and eg 99.999%-ile on the random choices.

> but still average over random choices your algorithm makes

Worst-case complexity is usually defined on Turing Machines or Von Neumann machines. In these models, algorithms cannot make "random choices", they are deterministic.

If you want to use a different computation model, you have to explicitly define it.

If you have a probability distribution, it is however possible to calculate the running time for different types of inputs and multiply those by the probability of the input being of that type to get an expected runtime which can then be expressed via O-notation.

I think this is well established practice, since there are a lot of interesting algorithms and data structures that have been widely studied and are probabilistic.

The analysis of probabilistic algorithms usually differentiates between inputs and random choices you make when running the algorithm.

You can analyze the worst case on the input while at the same time doing probability theory on the random choices. And since you control the random choice, you can impose nearly any reasonable distribution you feel like. (You just have to 'pay' for the generation of the random bits. Economizing on the number of random bits involved is just as much an area of research as economizing on runtime or memory.)

Of course, you can also analyze randomly distributed inputs. But that's a different beast, because in practice you seldom have a good handle on those distributions.

Fair enough, I'm not intimately familiar with how randomised algorithms are most often analysed in a very formal sense (I never saw an explicit theory of it, even though I've seen multiple more "intuitive" analyses). My point was more that there is no reason why you shouldn't be able to describe an expected runtime via O notation, whether or not that's the right way to do it in practice.

> Of course, you can also analyze randomly distributed inputs. But that's a different beast, because in practice you seldom have a good handle on those distributions.

But isn't this how it works for a hash table? It was my understanding that the actual hash function is deterministic, so there are no random choices to make - the randomness comes from the inputs; on the other hand you do have some assumptions (maybe not strictly proven) about the collision frequency, which should allow you to get a handle on the input distribution, or am I wrong?

In simpler times, hash maps used to be deterministic.

But that lead to easy denial of service attacks. So many languages, like eg Python, patched their hashmaps to use randomized hashes.

See eg https://arstechnica.com/information-technology/2011/12/huge-... or https://lwn.net/Articles/474912/ or https://bugs.python.org/issue13703

Now that you mentioned it, I remember running into this.

We would compute hashes out of some objects to compare for equality and it turned out we sometimes had more collisions than expected (orders of magnitude more), but this wasn't really reproducible. That was when I found out that the hashing algorithm wasn't deterministic. (Of course, the underlying cause was that our hash code calculations were not good and we had to fix them.)

> If you want to use a different computation model, you have to explicitly define it.

Probabilistic Turing machine are sufficiently standard and well known. They (or the random-access machine equivalent) are basically the implied context whenever you talk about randomized algorithm.

See https://en.wikipedia.org/wiki/Probabilistic_Turing_machine and https://en.wikipedia.org/wiki/Randomized_algorithm#Computati...

Worst case performance for the best compression algorithms result in an output file that's a few thousand bytes bigger than the input. And yet we are using compression to have this conversation.

It depends on what implementation of hash tables you use.

Especially if you use a randomized implementation.

Which is why we had a bunch of programming languages used for web servers scrambling to replace their hash algorithms with one that has better default key collision behavior and generates different output on every run.

Without upgrading your server you have the potential for someone to run a DDOS attack against you.

It depends on what implementation of hash tables you use.

> If you do a worst-case analysis, hash tables just degenerate to a single linked list (everything gets hashed to the same bucket), and you don't gain anything by using them. That's where you have 0(n) performance.

I don't gain anything from going outside because if you do a worst-case analysis I can get hit by lightning and die.

The worst case for a hashtable degenerating to a linked list can be often exploited to form a DOS attack. It is enough that user controls the keys inserted to the hashtable and the hash function is not cryptographically secure (typically they are not for performance reasons). That's why it is much wiser to use a binary tree for resolving collisions.

So in this case - the worst case analysis is useful.

Author here. Ah, that makes sense. I always took it for granted that such a scenario of everything hashing to the same bucket wouldn't happen, but I understand now that in such a scenario it would take linear time, which means that technically the _worst_ case is O(n).

However, I don't see that this influences the main point of the post. In practice, hash collisions are extremely rare, which means that the linked list inside the array slot is going to have few elements, and so we shouldn't be looking at the worst case time complexity of that linked list.

Even in the average case, hashtables can't really be constant. Simple proof: As elements are added, you either resize the table or you don't.[1]

Resize the table: a bigger table requires larger keys (to have a sufficient number of distinct ones), which require logarithmically more time to compute.

Don't resize the table: You have to stuff a logarithmic number of keys into each bucket and iterate over them.

Both increase time with input size.

Earlier discussion: https://news.ycombinator.com/item?id=9807739

[1] to clarify, I don’t mean resize on every addition. Just “you occasionally resize or you never do”.

How often do you resize your hash tables in your mental model? Maybe there's a better "resizing schedule" where you don't resize as often and the amortized time taken in the resizing is O(1) :)

What I’ve said is true even if you got the resizing for free.

Added a clarifying note. The point is, resizing is not the (only) problem.

Tangentially related question; what's best way to design a map/set that doesn't take O(n) time for resizing, considering memory locality?

Use an off-the-shelf database engine, sql or good enough nosql (like esent on windows).

Most file systems also have these properties, optimized for memory locality (because disk seeks were incredibly slow), and you can create files in a folder much faster than O(n).

If interested how they do it: https://en.wikipedia.org/wiki/B-tree

Yes, if you assume that your keys are going to be arbitrarily long inputs.

I think it's typical that in the analysis of algorithms we often make simplifying assumptions that we don't always spell out explicitly (and probably we should). The assumption here (which IMHO is often practically sensible) was that there is a certain fixed set of all possible keys, e.g. from a bounded set of integers. In that case, hash tables indeed have constant-time operations no matter how many elements you have.

I think it's a bit similar to saying that e.g. Gauss elimination is O(n^3). This is only true for fixed-size numbers, e.g. floats or bounded integer types, not for arbitrary integers - in fact, the Gauss algorithm is incredibly bad for true, arbitrary-precision arithmetic. Nevertheless, the algorithm is incredibly useful, because the fixed-size assumption is often warranted - the most notable exceptions are probably from the realm of cryptography.

>Yes, if you assume that your keys are going to be arbitrarily long inputs.

No, it only requires that they lengthen enough to be distinct for the keyspace size. The problem arises not from arbitrarily big keys but from the fact that, whatever your keys are, if want a longer output of the hash function, you have to do more computations on the keys.

Late follow-up: argh, I should really have been referring to values (the output of a hash function) rather than keys, because that determines where they go in memory block used for the hash table.

> If you do a worst-case analysis, hash tables just degenerate to a single linked list ... That's where you have 0(n) performance.

Even under a best-case analysis, hash table lookups are O(N) when using a single hash function. Assume you have a perfect hash function such that the N inputs are equally distributed among K output values (each of K gets (1/K)N values). Lookup will be O((1/K)N). O(CN) = O(N) for any constant C. (1/K) is constant, therefore lookups are O((1/K)N) = O(N).

> Out of that, we can compute that hash table operations are on average constant.

The only way you get constant time is if the number of collisions is bounded by some constant. That's not possible for arbitrary N when using a single hash function and constant K, as shown above.

Actual implementations try to improve performance by rebuilding the hash table as more items are inserted, using a new hash function with larger K. This can keep the linked list sizes bounded by some constant, which means O(1) lookups but at the cost of rebuild operations which are at least O(N). (Note: The optimal hash table is one in which K>=N with no collisions.)

This is the first time I've seen someone make this point (your first two paragraphs) besides me. One disagreement though:

>Actual implementations try to improve performance by rebuilding the hash table as more items are inserted, using a new hash function with larger K. This can keep the linked list sizes bounded by some constant, which means O(1) lookups but at the cost of rebuild operations which are at least O(N).

Even ignoring the rebuild operations, it's still not O(1), because if you use a different (evenly distributing) hash function with larger key size, you necessarily need more computations to compute K, and so lookup time increases.

> hash function with larger key size, you necessarily need more computations to compute K

You're right and I saw your other reply on this thread after I posted my reply. The time complexity is only O(1) if we ignore the cost of the hash function, which is really O(log N) because it needs to process at least log N bits. However, by that reasoning even an array lookup is O(log N) because an array lookup requires adding an offset to a base address and the addition function may require O(log N) operations to calculate.

According to some brief googling it appears that some (most?) sources avoid this problem by simply defining "elementary operations" to be O(1). A constant number of elementary options would also be O(1) by that definition. That is probably what is meant by those who say that a hash lookup is O(1).

But a (well-mixed) hash function must change to produce a larger output, requiring more elementary operations. That is, if you’re going to scramble the input, then you must do more operations to mix them as you increase the output size.

In contrast, the array does a single addition on a number that is larger, which seems different.

A simple hash function may be something like dividing by K and taking the remainder, which is probably considered an "elementary operation" by definition.

But in general, keys and the hash function could be anything. For example, if the keys are strings of length N, then it's O(N) for just calculating the hash. Or if the keys are bitmap images, the hash function could apply image recognition and use recognized features as hash values. So, textbooks and other sources probably just ignore the key size and hash function because they could be literally anything.

In order for it to be anything like an ideal hash function that evenly distributes the keys across buckets, it must be a "avalanche effect" hash function that mixes each byte with all the others. If you limit it to O(1) elementary operations, you can no longer have it operate that way, and are back to assuming significant collisions and iteration over them.

The hash functions used for hash tables are designed to be fast to compute and typically just involve a couple of operations. See, for example, this Stack Overflow answer about Python dict hash functions. https://stackoverflow.com/questions/8997894/what-hash-algori...

Yes, they fall short of being cryptographically secure hash functions, but the examples given in Python do force each byte to mix with all the other bytes. As long as you have to increase the size of the output (as the table gets bigger), you (eventually) have to increase the number of elementary operations in the hash function.

> And it hit me that it's actually O(n), because we've got an array and have to iterate over every element to see if the element matches char.

No, it's actually O(1). n refers to the _input_, which is always a single character. The iteration over an array (fixed at 5 elements) means a maximum of 5 comparisons. O(isVowel) = 5.

Javas implementation of HashMap uses a tree on hash collision.

[0] https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/...

If the bin is big enough to warrant it, according to your link.

Thanks for the link!

I imagine they do this as the user space can define hash algorithms and someone is gonna just return zero every now and then out of laziness :-)

You also need a comparable() key presumably - which you often have, but not always (a comparable() key is not strictly required by a hashtable).

It's not uncommon in scientific computing for the algorithm used to be automatically adjusted based on the input. An example of this is if you want to multiply very large integers. Karatsuba is first used, then Toom-Cook, then Schönhage–Strassen.

Karatsuba: θ(n^1.58)

Toom-Cook: θ(n^1.46)

Schönhage–Strassen: O(n log(n) log(log(n)))

Benchmarking is really the only thing that can reveal this kind of thing, otherwise you'll end up with a theoretically fast but practically slow algorithm.

Don't you need insanely high numbers before Karatsuba outperforms the simple O(n^2) algorithm? From Wikipedia:

> As a rule of thumb, Karatsuba's method is usually faster when the multiplicands are longer than 320–640 bits

4096-bit keys are standard for RSA, for example.

Another example is quicksort falling back to insertion sort as a recursive base case for some n=k (instead of recursing all the way to one element).

I see the "little N" argument often used to justify using high complexity (big O) algorithms.

But don't declare "little N" too early. If N depends on user input for instance, there is a high chance it might turn out bigger than expected. There are even attacks that exploit worst case complexity of algorithms.

For example, using a balanced tree as a way to deal with collisions in hash tables is not necessarily a stupid idea. If the table is overloaded or because of a poor or easily exploited hash function, your hash map will degenerate into O(log(n)) instead of O(n).

Now if you know for sure that collisions are unlikely, for example because you control the data you put into it, that you know that it will never be larger than a certain size, and that your hash function is good, then you can assume N is small.

That's why, when I doubt, I always consider N large. Using a O(log(n)) container may be a bit less efficient for low N, but it will not become catastrophic if N becomes big. If performance is needed and there is no guarantee about N, hybrid approaches are best, and that's how good libraries tend to work.

Usually N has to be really, really big before it matters, right? If so, it seems easy enough to tell when it won't reach that point.

https://jsben.ch/WCjjG

Well, seems like it does matter. Using an array is 50% slower than using an object and that's slower than using a Set in Chrome. Even worse in Safari. In Firefox array wins but you need to use a static array.

I don't know all the rules of JS. Semantically declaring an array in the function itself creates a new array on every invocation. Of course the JS engine should be able to figure out it doesn't need to create a new array every call but apparently Firefox's JS engine doesn't do that.

Note: I'm making the assumption we're talking about JavaScript since the code looked like JavaScript to me. I get that in another language the results might be vastly different.

> Well, seems like it does matter. Using an array is 50% slower than using an object and that's slower than using a Set in Chrome.

A 50% difference doesn't mean it matter. Unless this runs in some inner loop, just use the simplest solution.

I agree that if the fast solution is 10x the code then maybe choose another solution. In this case all 6 solutions are basically the same amount of code.

There's absolutely no reason to choose the slowest solution.

50% can easily be the difference between some VSCode extension making it sluggish vs not.

Further, in my experience slow solutions will eventually come back to bite you.

One I saw recenty. see if 2 arrays contain the same elements. The "simple" solution is sort copies of the arrays, concat them into strings, compare the strings. It looks simple but it's around 1000x slower than pretty much any normal but not 1 line solution. 1000x won't matter when you're testing your 5 element arrays in your unit test but it will matter then your users start using larger arrays.

At least in the blog post, the alternative solution has 10x the number of lines.

Of course, if you benchmark and this turns out to be important, try to optimize it.

And then it's a lot faster to use switch:

https://jsben.ch/U6w7l

Surprisingly byOr wins on Safari

You can do direct comparision, it's like 30x faster. There is cost of creating array, calling functions etc.

I've seen binary trees used for collision resolution in hash buckets in quite a few production systems. A pathological case of O(log n) is vastly better than a pathological case of O(n), if you care about it.

It might be instructive for programmers using higher level languages to learn about the cache hierarchy and the hardware prefetcher in modern systems. For those interested, I'd recommend reading Ulrich Drepper's classic: What Every Programmer Should Know About Memory[1].

[1]: https://www.akkadia.org/drepper/cpumemory.pdf

Related: linked lists are way overused in chaining hash tables when dynamic arrays could be used instead. One reason sometimes given is that linked lists are amenable to the "move-to-front" heuristic (move just-accessed element to the head of the list), but one can do the same thing in dynamic arrays by swapping the just-accessed element with the first element (a better heuristic though is to fix some k and swap with the kth element if the accessed element is outside the top k, or swap with the preceding element if it's in the top k).

This is why benchmarking is so important. It is the reality check you need.

Also... it took me decades to appreciate that clear code is better than fast code. If it’s slow, I can rewrite the inner loop. I’d rather have clear code with one thing optimized out of clarity that an entire system of clever code that I can’t debug.

For the value of "small-N" I am using 8 usually.

Here is why: https://terrainformatica.com/2017/10/15/when-linear-search-i...

And in Sciter objects (key/value maps) are using adaptive approach - if number of properties is less than 8 then it is linked list, otherwise - hash table.

A good rule of thumb is "if it fits in a cache line, then computation is free", where "computation" could mean search, hashing, compression, etc. This means, e.g., that linear search generally beats binary search if the whole array fits in a single cache line (or half a cache line if it's unaligned).

>This works because the elements in the array are close to each other in the physical memory. But with a hash, my understanding is that they wouldn't be so close, and thus we wouldn't benefit from this spatial locality effect.

By the same logic, when n is small, they will be close and benefit from cache locality as well.

Based on the specific example (hashing buckets for a hash map/table)… just use a hashing function that uses a random seed per map/table instance during hashing to prevent insertion attacks, eg. SipHash. This prevents an attacker from being able to purposely engineer the overloading of a single bucket with too many entries, allowing the implementer to use a standard linked list per bucket without worrying about external influences. Then, if you're still worried about the one in a trillion chance that a single bucket receives too many entries… yeah, you're over-engineering and wasting your own time, and the mental capacity of every developer who comes after you to try and understand your attempts to circumvent the problem in supposedly "smarter" ways.

There is something that must be said about anything that increases complexity in order to get efficiency:

1. It increases developer time.

2. It increases the number of bugs of the system as it increases enormously the different possibilities.

We have systems that actually meta program with Lisp our hash tables with different degrees of complexities.

It is already programmed, the designs already debug. And even then for most of our hash tables we just use the minimum level of complexity, that is having a memory that is 10 to 20 times bigger than the elements on the hash and just have one or two collisions for the entire set.

That way the code is way easier to understand, and the memory differences are just negligible(compared to the total amount of memory the program needs), if sets are well designed.

Here’s another article about O(n): 10 optimizations on linear search: https://queue.acm.org/detail.cfm?id=2984631

Thanks for this - very interesting small article

> The real point of this post is that when you have a little n, Big-O doesn't matter.

This is absolutely correct, however if this is done in a sufficiently generic programming language, there is a very good chance that falling back on a linked list on collision is a bad idea.

This has been well-researched and most programming languages have chosen a hash algorithm that resists (blind) collision generation, precisely for this reason.

I wrote some code recently to demonstrate this:

https://github.com/gergelykalman/bigOH

Nice article. Easy to argue about the details, because the author is describing what they've discovered or bumped into, not what they've studied. But I still think its a nice intro that may make other programmers think.

The article could explore open-addressing in hash-tables, and it could explore a switch statement for the vowels.

Tangent: I've often wondered where the double-hashing tables are, and whether they could use the high and low bits of a single hash rather than the low bits of two hashes...?

Honest question:

What would be the complexity of a function that took a string (or array of characters) and called this function on each character?

Would it be O(5n) ? Is that a thing? For each additional character in the input, it must compare against 5 values. Or would it be O(n) because it scales linearly?

Thanks in advance. I'm a front end engineer and this is my weakest area but I'm keen to learn. I've studied this before but I use it infrequently and it doesn't stick.

O(5n) is the same thing as O(n), because we ignore constant factors in O notation.

So, for a fixed size array of vowels, counting the vowels in a string is linear in the length of the string (it can't be sublinear, because we need to look at each character, and the straightforward algorithm is linear).

> O(5n) is the same thing as O(n), because we ignore constant factors in O notation.

Even better. f \in O(g) means there is some point and some factor after which f <= c*g. This means O(n²+21371232138091293n) and O(n²) are the same.

You'll need to be careful what your N is and what you're counting.

But lets assume the input is an array of n characters, n being an arbitrarily large but fixed positive number during a single invocation. And we're estimating the number of char compares.

Then, each invocation of isVowel(c) will do 1 - 5 compares. 1 in the case that c is the first element of the array, 5 if c is the last element or no element. As a worst-case estimation, isVowel(c) will do 5 compares at worst.

As such, if isVowel(c) is called for all elements of A, we will see between n compares (best case for all invocations) and 5*n compares (worst case for all compares).

As such, your algorithm has a worst-case runtime of O(5n) for all arrays A, which is a subset of O(n).

In practice and outside of academia, that's pretty much all you do:

- Identify your input set, and estimate its size

- Count how many loops are nested in the algorithm, call that L (1 in this case)

- Your algorithm should be O(n^L).

Once it gets into amortization and such... it becomes much harder.

nitpick, but O(5n) is not a subset of O(n), it is literally the exact same set.

That's still a subset ;)

Not a proper one though ;-)

My favourite: "You cannot sort floats faster than O(N logN)! It's been PROVEN!"

True story – I've heard this claim even from a CS PhD (!!).

This is what happens when you forget your assumptions and muddle your terminology. I politely directed him to radix sort [0].

[0] E.g. http://www.codercorner.com/RadixSortRevisited.htm

While this is correct about the theoretical effects of small N, an equally important factor in this day and age would be the cache. If that lovely little linked list causes O(N) cache misses through Java-style pointer-chasing... you are suddenly looking a a very slow hashmap.

Cache effects tend to mean that open addressing works out faster/more predictable in real world conditions.

Newbie question: why would a hash function ever result in hash collision? Why can't a hash function guarantee a unique output value?

A hash function has a limited range of outputs (e.g. for a hashtable it might be a number only a few bits large), whereas the space of possible inputs is larger or even unrestricted - e.g. could be arbitrary text.

If you have a space of possible inputs that isn't larger thant the outputs, then you can indeed design hash functions that do not collide.

Think what happens when the number of possible outputs is smaller than the number of possible inputs.

If we have a hash function f(n) that outputs a number between 1-100, but n can be any number between 1-1000, then some inputs must result in collisions.

Hash functions represent a chunk of data with fewer bits than the original data, hence there's always a _chance_ of a collision. With cryptographic hashes, the output of the hash function is relatively large in size, making the probability of an accidental hash collision vanishingly small. For example, sha-256 hash algorithm can result in over 115 quattuorvigintillion different values.

The hashing functions used with hash tables typically reduce the hashed value to one of only tens or hundreds of values, making collisions unavoidable. Typically, a hash table will try and manage the number of available slots to be roughly equal to the number of items stored in the hash to achieve performance that is a good balance of lookup time and memory requirements. For an extreme example, In Ruby, hashes of less than a certain size (6, I believe) are just represented internally as a list because the overhead of using an actual hash table is greater than just iterating through every item in the list.

Related: pigeonhole principle.

If you have n buckets, and n+1 items you're guaranteed to have a shared bucket.

In the case of hash algorithms you're taking an arbitrary sized input and "compressing" (in quotes because this is one way, you can't decompress it because of collisions) into a fixed size. If you permit more inputs to your hash function than there are hash values, then you will eventually have a collision.

A stupid awful hash function: n mod 100

So long as n is less than 100, you will never have a collision. But as soon as you compute the hash of n = 100, you will get a collision (with 0 in this case). Now, real world hash algorithms have larger spaces they map to, and more complicated mappings, but they all have this same problem. The larger the space (like 256-bits versus 64-bits) the less likely collisions become, but it could still happen.

In languages with a BYO hash function you might write a crap one, so having the tree on collision might still be handy.

In addition to this, for many applications, programmer time is more valuable than the asymptotic savings of a faster algorithm. This isn't as "pure" of a discussion since it now starts to involve money, but when viewing programs through the lens of creating business value, it's important to consider.

Even if this is true, don't say this loud. Because people have already taken it as license to write shitty code that is O(n²) where it can be O(n), or allocate in a frequently executed loop.

Great read. It's dangerous to overlook the practical aspects of the real-world hardware on which the code runs and over-index on the theoretical optimization.

Your convoluted O(1) implementation can be slower than a naive O(n) one if you're doing something practically time-consuming.

Why is there so much dark gray text on dark gray background? Impossible to read.

It's always worth remembering that O(n) describes the asymptotic limit where n is presumed to be very large (in fact, approaching infinity).

Related to this, there exist algorithms with impressive complexity-theoretic properties, but which are never useful in practice. They even have a cute name: https://en.wikipedia.org/wiki/Galactic_algorithm

"[...] premature optimization is the root of all evil [...]" D. Knuth

A heads up: if you use a dark theme in your phone, this webpage is recognizes it and changes its background to dark grey. This makes the grey words in the diagrams illegible.

Desktop too. At least on macOS, in both Firefox and Chrome.

Reply on news.ycombinator.com