Question

What is the value of jump taken for maximum efficiency while implementing jump search?

(a) n/2

(b) n^2

(c) n^1/2

(d) log n

I had been asked this question in a national level competition.

I need to ask this question from Searching topic in chapter Searching of Data Structures & Algorithms II

Answer 1

Correct choice is (c) n^1/2

For explanation: Total number of comparisons required will be n/k + k-1 in worst case. This function will be minimum for k=n^1/2. So this value of jump will be the best for implementing jump search.