What is the optimal block size for a Jump Search? Explain.

Consider a sorted integer array of size n with a block size of m. Jump Search would consecutively jump to its very last block searching for the target element, in turn causing an n/m number of jumps. Additionally, if the last element’s value of this block was greater than the target element, Jump Search would perform a linear search with m-1 comparisons.

This causes Jump Search to make (n/m) jumps with additional m-1 comparisons. Hence, the total number of comparisons will be (n/m+(m-1)). This expression has to be minimum, so that we get the smallest value of m (block size).

On differentiating this expression with respect to m and equating it with 0, we get:

n/-m2+1 = 0
n/m2 = 1
m = √n

Hence, the optimal jump size is √n, where n is the size of the array to be searched or the total number of elements to be searched.