explain! Prev post >> Congestion control Next post >> New mobile app for GATE Overflow released Anil Khatri posted Aug 28, 2016 Anil Khatri 1,984 views 0Like0Love0Haha0Wow0Angry0Sad comment 19 Comments See all 19 Comments See all 19 19 Comments reply - commented Aug 28, 2016 Like reply Follow Share 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) Anil Khatri commented Aug 28, 2016 Like reply Follow Share 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!!! - commented Aug 28, 2016 Like reply Follow Share 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 Akanksha Kesarwani commented Aug 28, 2016 Like reply Follow Share Ο(n^2) .. Prashant. commented Aug 28, 2016 Like reply Follow Share do counting sort . Shivangi Verma commented Aug 28, 2016 Like reply Follow Share 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) Ritaban Basu_23 commented Aug 30, 2016 Like reply Follow Share Use hashing .. It would O(n) since nothing is mentioned about space complexity we can do it in O(n) Anil Khatri commented Aug 30, 2016 Like reply Follow Share how is it implement using hashing? - commented Aug 30, 2016 Like reply Follow Share each value in array is considered as key and the value is no of times that integer has appeared in the array . anonymous commented Sep 8, 2016 Like reply Follow Share 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 Sushant Gokhale commented Sep 9, 2016 Like reply Follow Share @Ritaban. Even I thought of hashing. But space requirement is confusing me. alkber commented Oct 14, 2016 Like reply Follow Share 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. Sushant Gokhale commented Oct 15, 2016 Like reply Follow Share @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). anonymous commented Oct 15, 2016 Like reply Follow Share 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. Sushant Gokhale commented Oct 16, 2016 Like reply Follow Share @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. alkber commented Oct 16, 2016 i reshown by alkber Feb 14, 2017 Like reply Follow Share 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 ? Sushant Gokhale commented Oct 16, 2016 Like reply Follow Share @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 :) ravi_ssj4 commented Feb 3, 2017 Like reply Follow Share why are people posting questions as blogs ? Aboveallplayer commented Feb 3, 2017 Like reply Follow Share 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 Please log in or register to add a comment.