Question

What will be the time complexity of update query operation in an array of size n when we use square root optimization?

(a) O(√n)

(b) O(n)

(c) O(1)

(d) O(n^2)

The question was posed to me by my school teacher while I was bunking the class.

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

Answer 1

The correct option is (c) O(1)

The best I can explain: The time complexity of query operation remains the same in both square root optimized code and non optimized code. We simply find the chunk in which the update requires to be performed and then add the new updated value at the desired index.