CareerCup

What is the need of sorting the array for finding maximum number..
Its possible in O(n) only..
max=0;
REP(i,n)
{
if(arr[i]>max)
max=arr[i];
}
print max;

Merge Sort, the complexity is n(log n)

Idea you are right or Question itself is wrong.

I think the question is correct as well as "idea's" answer is correct. So essentially you would use Bubble sort approach for just one iteration. One iteration of merge sort approach wont give you the answer.

I agree, you would use Bubble sort (1 pass) which will bublble the max element at the last/first position and return that index. But what if the array size is > 1000?

Hi Tom i havn't understand what u are trying to say? Anyway it requires one full iteration o(n)

I'm not able to figure out why people are hell-bent on using some kinda sort techniques just to get the max of the list...just iterate over the list keeping track of the max seen so far...as mentioned by 'nav'...thats it...O(n) solution...no question of thinking about any sorting techniques...

the question was actually asked to test the understanding that in i th iteration in bubble sort we get i th maximum for sure.

the question is which among bubble sort and merge sort which one is better... its not the question of HOW to find max of array... well everyone knows the answer.

the second part of the question says if array length is more than 1000 ... some people still are doubtful its bubble sort or merge sort ....... may be this question is to sort those people out of the list of "possible candidates" :P, has anyone here replying here passed the test??

I think the answer is pretty straight forward, it would be bubble sort. Lets start with a simple thing, bubble sort takes o(n^2) time complexity but 0(1) space complexity where as merge sort takes O(nlogn) time and o(n) space complexity. Though bubble sort would take O(n^2) worst case, we will never experience that because we just have to find the maximum element hence whether array is < 1000 or more than 1000, bubble sort would be preferred. If you want the entire array to be sorted then merge sort is definitely a good solution but in case of maximum element, bubble sort is your best friend

John, you're right that bubble sort is what you'd choose (if you were trying to over-complicate it), but that's a long way from saying that bubble sort is your best friend. Want to find the max element? Do a linear scan for the largest element. Done. O(n). One loop.

This is nothing but an idiotic question designed to trip people up based on wording and their tendency to move quickly through questions on a timed test.