4 ms·

> 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

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

eru 6y ago
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.
- progval 6y ago
  > 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.
  - Tainnor 6y ago
    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.
    - eru 6y ago
      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.
      - Tainnor 6y ago
        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?
        eru 6y ago
        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-portions-of-web-vulnerable-to-hashing-denial-of-service-attack/ https://arstechnica.com/information-technology/2011/12/huge-... or https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ or https://bugs.python.org/issue13703 https://bugs.python.org/issue13703
  - eru 6y ago
    > 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 https://en.wikipedia.org/wiki/Probabilistic_Turing_machine and https://en.wikipedia.org/wiki/Randomized_algorithm#Computational_complexity https://en.wikipedia.org/wiki/Randomized_algorithm#Computati...
hinkley 6y ago
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.

eru 6y ago

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.

progval 6y ago
> 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.
- Tainnor 6y ago
  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.
  - eru 6y ago
    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.
    - Tainnor 6y ago
      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?
      - eru 6y ago
        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-portions-of-web-vulnerable-to-hashing-denial-of-service-attack/ https://arstechnica.com/information-technology/2011/12/huge-... or https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ or https://bugs.python.org/issue13703 https://bugs.python.org/issue13703
- eru 6y ago
  > 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 https://en.wikipedia.org/wiki/Probabilistic_Turing_machine and https://en.wikipedia.org/wiki/Randomized_algorithm#Computational_complexity https://en.wikipedia.org/wiki/Randomized_algorithm#Computati...

hinkley 6y ago

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.