My AP Computer Science class recently learned about hash tables and how linear probing resulted in issues with clustering and turned out to not really be constant time insertion/searching. Our instructor told us that quadratic probing would be a good way to reduce clustering for obvious reasons. I wondered if it would be possible that if there was one element left, it would take a while for quadratic probing to find it. I wrote a quick program (I can insert the source if you want, but I don't think anyone will read it anyway) that tested to see if this happened.
First, I proved that if there isn't an array index that will never be landed on, it will be found if you always try to add to any one index. This is because by doing this, it will either eventually hit every index in the array, or it won't. If quadratic probing hits every index, then you could have picked any index at any point and it always would have ended, so that length array always works. If it can't hit every instance, you would have found what you can't do doing this.
Then, I made an array of booleans of whatever length I was interested in, and if index 0 wasn't true, set it to true, otherwise set index 1%length to true if it wasn't otherwise set index 4%length to true if it wasn't ... otherwise set index n%length to true if it wasn't...
I did not check 1 forwards and 1 back, but as you will see this wouldn't have mattered in the first place.
So, in an array of four elements, quadratic probing will find indexes 0 and 1, but (within about 46000^2 % length) never got to indexes 2 or 3. If I had gone backwards as well, it would have found index 3 (((0-1)%4+4)%4==3), but still not index 2.
After a bit of thinking I found that I was looking to see if there was any pair of numbers, x and n, where both x and n are integers, where the following equation evaluates to true:
x^2 == 4*n+2
That is, two more than 4 times any integer is a square number.
If it can be proven for all integers x and n that there is no pair that will result in that being true, that means quadratic probing will never get to index 2 in an array of length 4.
I think this is the same thing as saying that the parabola:
y=(x^2-2)/4
contains no (x, y) pair where both x and y are integers, but I am not entirely sure.
I've just spent the past two hours working on this and this is all I've been able to figure out.
I know that there are times when quadratic probing doesn't find a spot; that isn't what I am interested in. How would I go about proving that either this will never work, or that, if I use large enough numbers, this will eventually terminate. Also, if you could keep the math under stuff you learn in BC Calculus, that would be great.
Thanks very much!
Okay, after quite a bit of thinking, I think I have the solution, and I thought I would post it here in case anyone else had the same question. In the specific example given above (i. e. index 2 in a table of length 4), the program will indeed go forever. In order for it to stop, it would need to be true that there is some integer x for which x^2 - 2 is divisible by 4. The solution I found comes from the properties of even and odd numbers. I think this is easy to understand, but not really applicable to other cases, so I would still appreciate a general answer.
x^2 - 2 is even if and only if x^2 is even, because subtracting 2 from a number will not change whether or not it is even.
Note: We cannot say that there are no even square numbers, as every other square number is even.
x^2 is a perfect square because x is an integer. That means that if one were to write out the prime factorization of x, it would have an even exponent above each of its factors. This is because a perfect square is created by multiplying the same number by itself.
As stated in the question, we are looking to prove that there is no integer for which 4*n + 2 is a perfect square. Now, 4*n + 2 must not be a multiple of 4 [it is two more than a multiple of four, of course]. Therefore, we are trying to prove that every perfect square that is a multiple of 2 is also a multiple of 4, which means there will be no instance for which two more than a multiple of 4 is a perfect square, because all perfect squares have been proved to be multiples of 2.
Since every square number has an even number of every one of its factors, it must be a multiple of 2 to an even power, and not an odd one. If it is indeed a multiple of 2 to a power greater than 1, it is also a multiple of 4. Any square number with any factor of two at all must have a second factor, because that factor of two could only have possibly come from one of the two numbers that were multiplied together to get that perfect square. Since those numbers must have been equal, either they both had a two and the number is a multiple of 4, or neither did, and it is not even even in the fist place.
Therefore, in the hashtable mentioned above, quadratic probing will never terminate, because it will never find that spot. Also, sorry for the mathy answer, I would have preferred a computer science one, but the theory for Comp. Sci. starts to drift into the mathematical zone slightly when you get to proving things.