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(log n)

• A. O(n log n)

100. O(n)^2

500. 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? 

Comments

They should have mentioned something about the algorithm right?

---

unfortunately, they did not mention anything else nor did they specify any algorithm

---

@muthu kumar

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)

---

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?

---

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)

---

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

---

@muthu kumar

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

---

Yes, bro that is the query with us. worst case == bubble sort ??

---

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

---

Ya use stl or use hashing.....................u will get in O(n) time

---

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

---

Thanks a ton! Will keep that in mind :D

---

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.

---

I think the question is ambigous.

---

@kumar.dilip

Can you please take an example and explain..

---

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

---

@garimanand

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

 

---

@MiNiPanda Isn't the TC of the algorithm you mentioned is $O(n^2)$? 

---

@MiNiPanda

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

 

---

@gauravkc

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

---

and either loop runs n times or 2n-1 times it is O(n). Right?

---

@Verma Ashish Yes but i ran it for n times only na? Did I go wrong anywhere?

---

@MiNiPanda 

for i loop runs n times(for sure), in your example only one pair is present such that difference is 7(=k).  

in worst case difference between nth and (n-1)th element is k.. So j will run upto (n-1). And loop runs =2n-1 time. 

i don't know whether i got u right or not?

---

Here we have nc2 possible pair for each pair we have to see difference and  traverse all again to count such pair ,how ?nlogn is possible we have to use dynamic paradigm to solve it where extra  space equal to lower triangular matrix which is almost equal to n2

Answer 1

you have to always mark worst case TC which will be O(n2)

Comments

It ask for worst case of best possible algo..