# MadeEasy Test Series 2018: Algorithms - Time Complexity

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)

edited
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
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?

## Related questions

1 vote
1
202 views
Can someone work this out?
2
137 views
Consider the following graph and sequences given below : Given answer for no of DFS traversal was 2 : S1 and S2. How S2 is a DFS traversal ?
3
121 views
For a directed graph, the absence of back edges in a DFS tree can have cycle. true or fale.please explain with an example.
1 vote