5 ms·

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
        > 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 https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle
- progval 6y ago
  > 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
eru 6y ago
It depends on what implementation of hash tables you use. Especially if you use a randomized implementation.
hinkley 6y ago
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.

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
      > 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 https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle
progval 6y ago
> 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

eru 6y ago

It depends on what implementation of hash tables you use. Especially if you use a randomized implementation.

hinkley 6y ago

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.