0

This is a similar question to Linear Probing Runtime but it regards quadratic probing.

It makes sense to me that "Theoretical worst case is O(n)" for linear probing because in the worst case, you may have to traverse through every bucket(n buckets)

What would runtime be for quadratic probing? I know that quadratic probes in a quadratic fashion -1, 4, 9, 16, ..... My initial thought was that it's some variation of log n(exponential) but there isn't a consistent base.

Community
  • 1
  • 1
committedandroider
  • 8,711
  • 14
  • 71
  • 126

1 Answers1

1

If there are n - 1 occupied buckets in your hash table, then regardless of the sequence in which you check for an empty bucket, you cannot rule out the possibility that you will need to test n buckets before finding an empty one. The worst case for quadratic probing therefore cannot be any better than O(n).

It could be worse, however: it's not immediately clear to me that quadratic probing will do a good job of avoiding testing the same bucket more than once. (That's not an issue with linear probing if you choose a step size that is relatively prime to the number of buckets.) I would guess that quadratic probing doesn't revisit the same buckets enough times to make the worst case worse than O(n), but I cannot prove it.

John Bollinger
  • 160,171
  • 8
  • 81
  • 157
  • But is there under the assumption that you are working with a circular array? – committedandroider Mar 14 '15 at 18:29
  • Circularity has nothing to do with it. Any technique that tests buckets in a fixed sequence (which is necessary for finding elements after they are added) -- whether absolute or relative to the starting bucket -- may in principle test every occupied bucket before it finds an empty one. If quadratic probing has any advantage then it would be in reducing bucket clustering. That may be an advantage for *average* run time, but not for worst-case run time. – John Bollinger Mar 16 '15 at 16:33