What is the worst case time complexity to count pairs of numbers with difference ‘k’ from an input array of ‘n’ numbers?
a) O(logn)
b) O(nlogn)
c) O(n^2)
d) O(n^2logn)
MAY TAKE O(n2)
ANOTHER PART JUST SORT THE ARRAY AND THEN FIND O(nlogn)
@ Ashwin Kulkarni As worst case complexity is asked shouldn't we just iterate outer loop from 0 to 'n-1' and the inner loop from i+1 to n? What was your algo behind nlogn?
@Anu007 But won't that be the Best Case?