MadeEasy Test Series 2018: Algorithms - Time Complexity

Question

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)

Comments

O(nlogn) ??

---

O(n^2)??

---

MAY TAKE O(n²)

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?

---

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.

---

Answer given is : O(nlogn)

---

Use merge sort for sorting. In worst case O(nlogn) & O(nlogn) to find x-y = k.

---

But what is the need to sort if Worst Case Time complexity is asked?

---

Worst case of best algo?