Question

Total how many iterations are required to find the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?

(a) √n

(b) 2*√n

(c) 3*√n

(d) n*√n

This question was posed to me in an interview for internship.

This key question is from Miscellaneous in portion Miscellaneous of Data Structures & Algorithms II

Answer 1

Right choice is (c) 3*√n

Easiest explanation - After calculating the sum of each chunk individually we require to iterate only 3*√n times to calculate the sum in the worst case. It is because two of the √n factors consider the worst case time complexity of summing elements in the first and last block. Whereas the third √n considers the factor of summing the √n chunks.