6 ms·

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

Tainnor 6y ago
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.
- josephg 6y ago
  > 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.
  - Tainnor 6y ago
    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.
    - eru 6y ago
      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.
      - Tainnor 6y ago
        This is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.
        eru 6y ago
        I just searched for 'polynomial time simp lex algorithm' and found things like eg https://cstheory.stackexchange.com/questions/2373/complexity-of-the-simplex-algorithm https://cstheory.stackexchange.com/questions/2373/complexity... which references https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc....
        Tainnor 6y ago
        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.
        eru 6y ago
        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.
    - josephg 6y ago
      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_science https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...
nurumaik 6y ago
No, they are not amotrized constant time because there is some predefined sequence of inputs that makes them always work in linear time
- FeepingCreature 6y ago
  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.
  - josephg 6y ago
    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.
    - eru 6y ago
      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.)
      - BeetleB 6y ago
        > 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)
eru 6y ago
It depends on what implementation of hash tables you use.

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.

josephg 6y ago
> 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.
- Tainnor 6y ago
  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.
  - eru 6y ago
    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.
    - Tainnor 6y ago
      This is interesting, do you happen to have a reference? I couldn't find anything by a quick google search.
      - eru 6y ago
        I just searched for 'polynomial time simp lex algorithm' and found things like eg https://cstheory.stackexchange.com/questions/2373/complexity-of-the-simplex-algorithm https://cstheory.stackexchange.com/questions/2373/complexity... which references https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc.pdf https://www.cs.yale.edu/homes/spielman/Research/SimplexStoc....
        Tainnor 6y ago
        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.
        eru 6y ago
        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.
  - josephg 6y ago
    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_science https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...

nurumaik 6y ago

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

FeepingCreature 6y ago
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.
- josephg 6y ago
  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.
  - eru 6y ago
    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.)
    - BeetleB 6y ago
      > 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)

eru 6y ago

It depends on what implementation of hash tables you use.