The Gateway to Computer Science Excellence
+1 vote
170 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 by Junior (823 points)
edited by | 170 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.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
198,265 comments
104,979 users