I am currently learning about searching algorithms and I came across jump search, which has a time complexity of O(√n). Why is √n the optimal value for m (jump size) in the jump search algorithm and how does it affect the time complexity?

CodePudding user response：

Let m be the jump size and n be the number of elements.

In the worst case, the maximum number of elements you have to check is the maximum number of jumps (n/m - 1) plus the number of elements between jumps (m), and the time you take is approximately proportional to the total number of elements you check.

The goal in choosing m, therefore, is to minimize: (n/m) m-1.

The derivative by m is 1 - (n/m²), and the minimum occurs where the derivative is 0:

1 - (n/m²) = 0

(n/m²) = 1

n = m²

m = √n

CodePudding user response：

Assuming the block size is k, the worst case scenario requires roughly n / k iterations for finding the block and k iterations for finding the element in the block.

To minimize n / k k where n is a constant, we can use differentiation (see Matt's answer) or the AM-GM inequality to get:

n / k k >= 2sqrt(n)

We can clearly see that 2sqrt(n) is the minimal number of iterations and is attainable when k = sqrt(n).