gatebook_dsa

Question

explain!

Comments

Apply merge sort on the array .That will take O(nlogn) .Then finding the pair of integers that are same will take O(n)

O(nlogn) + O(n) =O (nlogn)

---

if we have an array of size n and also take another array of size n which is initially empty

then first take a[0] from original array and put it into new array thenn take a[1] from original array and compare with new array's elements and so on

if we comapre original array' element with new array element and find in it then element is duplicate

so time complexity =O(n) and space complexity =O(n)

correct if wrong!!!

---

suppose the array is 1,2,3,4,5,6,5

In this case after comparing first element with other element ,you will not get the pair ..you have to compare other elemnts likewise too.that's why it will take O(n^2) not O(n).

 

For your case it will only work if you have array as :1,1,3,4,4

---

Ο(n^2) ..

---

do counting sort .

---

It is basicaly searching and comparing but no sorting ...I think it shud be O(n) since here worst case complexity is asked and since no swaps i think it shud not be O(n^2)

---

Use hashing .. It would  O(n) since nothing is mentioned about space complexity we can do it in O(n)

---

how is it implement using hashing?

---

each value in array is considered as key and the value is no of times that integer has appeared in the array .

---

i think it should b n^2 as they are asking for worst case  and worst can  be  .. selection a element  and searching  for the  same other element in n elements . n times .. so in worst  case it will take n^2 time to select pair of  same element

---

@Ritaban. Even I thought of hashing. But space requirement is confusing me.

---

Worst case is not finding the equivalent element. 

[ 3 , 5 , 4 , 5 , 8 ,  9, 1]

The algorithm works by, compairing a each element with all the array elements.

for( i = 0; i < n ; i++)

   for (j = 0; j < n ; j++)

        if ( i != j && arr[i] == arr[j] )

                          break;

So, here,  first loop runs for n times, second loop runs for n times for each n of first loop. Since the quest is about time complexity, space complexity can be ignored.

So, total iterations this loop would run is n*n = n^2 , O(n^2) should be the answer. Correct me if i'm wrong. 

 

 

 

---

@Althaf.

Rather than comparing, I would sort the array and then the elemrnts would be adjacent.

So, O(nlogn + n) = O(n.logn).

But since, there is no memory constraint (since it would have been given), It can be done by hashing in O(n) or worst O(n.logn).

---

Hi, sushant, as the nature of algorithm isn't mentioned. Isn't may analysis right,, for the algorithm i mentioned ? I understood your approach, that seems to be right if it is sorted.

---

@anonymous.

Its asking for the time complexity in worst case using the best algorithm. Its not time complexity using the worst algorithm :)

For example, I can transform Dijkstras algorithm into other algo such that it takes polynimial/exponential time for running. THat doesnt mean worst case time complexity is polynomial/exponential.

---

Hi Sushant, i'm entirely new to gate questions. Was aware this algorithm is the worst kind. However, are we suppose to have wild assumptions ? I mean, question doesn't specify, if it meant for an algorithm of smaller input size or larger input size since there are algorithms that does well for smaller sizes.

So here which algorithm are we suppose to assume ? Some are saying it should be sorted, while others say it need not. I may be missing something.  

So, i strongly believe that, questions having soo much assumptions which would vary with person to person, isn't a good fit. Am i right ?

---

@altaf.

Make minimum assumptions. Assumption is what you feel :). It may not be the best.

Make assumptions only to the point of deriving the answer or mandatory for deriving the answer. If assumption is giving you best answer, hold it.

You should think of the best algorithm because no one will ask you whats the worst algorithm :)

---

why are people posting questions as blogs ?

---

Hashing solves it in O(n) time ..and if hashing is not prmitted then sorting by nlogn time

ps: post queries as a question..not as a blog