search
Log In
1 vote
281 views

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)

in Algorithms
edited by
281 views
0
O(nlogn) ??
0
O(n^2)??
0

MAY TAKE O(n2)

ANOTHER PART JUST SORT THE ARRAY AND THEN FIND O(nlogn) 

0

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

@Anu007 But won't that be the Best Case?

0
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.
1
Answer given is : O(nlogn)
0
Use merge sort for sorting. In worst case O(nlogn) & O(nlogn) to find x-y = k.
0
But what is the need to sort if Worst Case Time complexity is asked?
0
Worst case of best algo?

Please log in or register to answer this question.

Related questions

2 votes
1 answer
2
2 votes
0 answers
3
...