Question

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s.What will be the time complexity???????

Answer 1

O(1)  since the array is sorted we have to find the sum of first two elements only if their sum is less than 1000 than output will be yes if not than since the elements are sorted if the sum of first two elements is not less than 1000 than the sum of no two elements would be less than 1000 and output would be no.

Comments

so if in one check we determine that order is descending then it should be O(N) ???

---

Yes. You are correct arjun sir. Thank you!

First of all compare the first and last elements of the array to know whether the array is ascending or descending order. If the first element is less than the last then it is in ascending order. Otherwise it is in descending order.

If it is in ascending order add the first two elements to see whether the sum is greater than 1000. If not then the output will be NO.

Same is the case with descending order. Add the last two elements to see whether their sum is greater than 1000 or not. If not then the answer will be NO. Otherwise it is YES. So in O(1) we can find.

---

Time complexity will be O(1)

as we will only check first 2 elements of the array and if there sum is <1000.

So 1 comparison constant time.

So, O(1)

Answer 2

o(n)

Comments

@arjun sir , what if we have find all such elements ??

---

Sir @arjun Sir If the elements are unsorted then the T.C would be O(N), right? Correct me if I’m wrong or any other soln.?