explain!

The Gateway to Computer Science Excellence

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

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

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

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)

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

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.

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 ?

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 :)

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 :)

- All categories
- Testimonials 64
- Numerical Ability 0
- Verbal Ability 1
- Engineering Mathematics 13
- Algorithms 3
- Databases 5
- Digital Logic 4
- CO & Architecture 4
- Computer Networks 4
- Compiler Design 3
- Programming & Data Structures 6
- Motivation 25
- Preparation Advice 72
- Theory of Computation 7
- Study Materials 46
- Others 218
- Interview Experience 89
- Preparation Experience 42
- Useful Links 27
- Announcements 103
- Jobs 4

50,648 questions

56,459 answers

195,334 comments

100,182 users

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