1 vote

What is the worst case time complexity to count pairs of numbers with difference ‘k’ from an input array of ‘n’ numbers

- O(log n)

- O(n log n)

- O(n)^2

- O(n^2 log n)

The answer given was B but since worst case time is stated shouldn't the answer be C? I mean we can check all possible pairs in the worst case. Correct me if I am wrong?

0

no need to mention about algo .

first we have to sort the array which will take O(nlogn).

now , take two pointers first fix the first pointer on the first element and then increse the second pointer till difference >=k , thn correspondingly increase first pointer .

so it will take O(n) time

so total time = O(nlogn)

0

What if all possible pairs are computed? The question clearly states WORST CASE TIME complexity! All possible pair gives O(n^2). Why is that wrong?

0

thats what i have said u can jst have a count variable and whenver difference of two pointers = k ;u can increase count value by 1 . which can be done iin O(n)

0

Bro, I agree with u. But we can use bubble sort algorithm and also using count inside that we can able to count all possible pairs right??

0

u cant use bubble sort becoz input array might be in descending order then it will take O(n2), so better use merge sort to sort the array

3

worst case does not mean we have to use worst possible algorithm in general it means

the worst case of the most efficient algorithm...

we can do this in O(n) time by using hash map but it only works for small ranges

so in it can be done by BST or sorting (best possible sort eg. merge )

in that case worst case time complexity will be O(nlogn)

source https://www.geeksforgeeks.org/count-pairs-difference-equal-k/

although as far i know we can do this for long ranges in O(n) time by using map in stl library

2

Whenever such questions are asked we need to find out the best algo (that is the most efficient one) which can help us in getting the result.

By worst it means the worst case scenario when we use this most efficient algo.

There is no meaning if they ask us for the unoptimized algo because that doesn't test our ability of thinking.

Here once we sort the algo using merge sort, if the difference b/w the first 2 elements=k then that is the best case and if the difference b/w the last 2 elements is k then that is the worst case as we have to increment the i and j pointer throughout the sorted array.

Eg: let the sorted array be 1,2,4,11 and k=7

i and j both point to 1.

|ar[i]-ar[j]|=| 1-1 |=0 but 0<k so j++

|ar[i]-ar[j]|=| 1-2 |=1 but 1<k so j++

|ar[i]-ar[j]|=| 1-4 |=3 but 3<k so j++

|ar[i]-ar[j]|=| 1-11 |=10 but 10>k so i++

|ar[i]-ar[j]|=| 2-11 |=9 but 9>k so i++

|ar[i]-ar[j]|=| 3-11 |=8 but 8>k so i++

|ar[i]-ar[j]|=| 4-11 |=7 but 7==k FOUND!!

So in this case we have to shift the variables for the max no. of times hence the worst case

By worst it means the worst case scenario when we use this most efficient algo.

There is no meaning if they ask us for the unoptimized algo because that doesn't test our ability of thinking.

Here once we sort the algo using merge sort, if the difference b/w the first 2 elements=k then that is the best case and if the difference b/w the last 2 elements is k then that is the worst case as we have to increment the i and j pointer throughout the sorted array.

Eg: let the sorted array be 1,2,4,11 and k=7

i and j both point to 1.

|ar[i]-ar[j]|=| 1-1 |=0 but 0<k so j++

|ar[i]-ar[j]|=| 1-2 |=1 but 1<k so j++

|ar[i]-ar[j]|=| 1-4 |=3 but 3<k so j++

|ar[i]-ar[j]|=| 1-11 |=10 but 10>k so i++

|ar[i]-ar[j]|=| 2-11 |=9 but 9>k so i++

|ar[i]-ar[j]|=| 3-11 |=8 but 8>k so i++

|ar[i]-ar[j]|=| 4-11 |=7 but 7==k FOUND!!

So in this case we have to shift the variables for the max no. of times hence the worst case

0

It can be done in O(n) time.

you can do that array like this

arr[i] = k - arr[j];

Just find that difference in the array. that's it.

you can do that array like this

arr[i] = k - arr[j];

Just find that difference in the array. that's it.

0

By sorting method we get O(nlogn) and using hashing it will be O(n). Then which option we should mark as correct??

0

In the link you attached its given that O(n) is the **average** time complexity not the worst.

Also, the number of elements has to be known before hand. I don't think we can take help of library functions to find the complexity in Gate atleast.. :P

0

i have mentioned it that this link says O(n) only of small ranges

but using stl map we can use it even for long ranges

0

If you see it again, I have incremented either i or j in each iteration out of n iterations i.e. in 1 scan