1 votes 1 votes 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) Algorithms algorithms time-complexity made-easy-test-series madeeasy-testseries-2018 + – charul asked Jan 12, 2018 • edited Mar 5, 2019 by ajaysoni1924 charul 733 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Ashwin Kulkarni commented Jan 12, 2018 reply Follow Share O(nlogn) ?? 0 votes 0 votes vishal chugh commented Jan 12, 2018 reply Follow Share O(n^2)?? 0 votes 0 votes Anu007 commented Jan 13, 2018 reply Follow Share MAY TAKE O(n2) ANOTHER PART JUST SORT THE ARRAY AND THEN FIND O(nlogn) 0 votes 0 votes vishal chugh commented Jan 13, 2018 reply Follow Share @ 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? 0 votes 0 votes vishal chugh commented Jan 13, 2018 reply Follow Share @Anu007 But won't that be the Best Case? 0 votes 0 votes Ashwin Kulkarni commented Jan 13, 2018 reply Follow Share Yes sort the array and then we can find x-y = m in O(n) time but sorting will take O(nlogn) but worst case sorting might go upto O(n^2) too. 0 votes 0 votes charul commented Jan 13, 2018 reply Follow Share Answer given is : O(nlogn) 1 votes 1 votes Rohit Gupta 8 commented Jan 13, 2018 i edited by Rohit Gupta 8 Jan 13, 2018 reply Follow Share Use merge sort for sorting. In worst case O(nlogn) & O(nlogn) to find x-y = k. 0 votes 0 votes vishal chugh commented Jan 13, 2018 reply Follow Share But what is the need to sort if Worst Case Time complexity is asked? 0 votes 0 votes Rohit Gupta 8 commented Jan 13, 2018 reply Follow Share Worst case of best algo? 0 votes 0 votes Please log in or register to add a comment.