3 ms·

> but still average over random choices your algorithm makes Worst-case complexity is usually defined on Turing Machines or Von Neumann machines. In these mode

> 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
      - Tainnor 6y ago
        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.)
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...

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
    - Tainnor 6y ago
      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.)

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