Question

What will be the worst case time complexity of code to find sum in given query range (l,r) in an array of size n with q number of such queries?

(a) O(n)

(b) O(q)

(c) O(n*q)

(d) O(n+q)

I have been asked this question in an online quiz.

The above asked question is from Miscellaneous topic in portion Miscellaneous of Data Structures & Algorithms II

Answer 1

Right answer is (c) O(n*q)

Easy explanation - For finding the result of one query the worst case time complexity will be n. So for q queries the time complexity will be O(q*n). This can be reduced by using square root optimization.