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?

(a) O(n)

(b) O(l+r)

(c) O(l-r)

(d) O(r-l)

This question was addressed to me during a job interview.

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

Answer 1

Correct answer is (a) O(n)

For explanation: For a given array of size n we have to traverse all n elements in the worst case. In such a case l=0, r=n-1 so the time complexity will be O(n).