Question

What will be the worst case time complexity of finding the sum of elements in a given range of (l,r) in an array of size n when we use square root optimization?

(a) O(n)

(b) O(l+r)

(c) O(√n)

(d) O(r-l)

This question was posed to me during an interview.

I need to ask this question from Miscellaneous in section Miscellaneous of Data Structures & Algorithms II

Answer 1

Correct choice is (c) O(√n)

The best explanation: When we use square root optimization we decompose the given array into √n chunks each of size √n. So after calculating the sum of each chunk individually, we require to iterate only 3*√n times to calculate the sum in the worst case.