If there is a N sorted array then what is time complexity of finding 2 numbers with sum less than 1000.
A) O(1) B) O(n^2) C) O(n) D) O(logn)

• O(n^2) as N is the order of the array we have to iterate from first to the last so we get N*(N+1)=N^2+1 which is n^2
• 4 years agoHelpfull: Yes(0) No(0)
• O(n) using two pointers one at the start and other at the end .. need to check below criteria
  if arr[start] + arr[end] == 1000 :
  break
  else if arr[start] + arr[end] > 1000:
  end -= 1
  else arr[start] + arr[end] < 1000:
  start += 1
• 4 years agoHelpfull: Yes(0) No(0)
• The answer is A.
  It will take constant time as the minimum sum possible would be the sum of the first two numbers.
  If that sum is less than 1000, then there exists a pair and if not 1000 then no such pair exists.
• 4 years agoHelpfull: Yes(0) No(0)