Most efficient way to get the highest number from a collection of integers

Question

Question:Most efficient way to get the highest number from a collection of integers

I was recently discussing this question, I had 2 solutions in mind. 1) Iterating over the collection and find the highest number (code below) 2) Use a sorting algorithm.

The first method will have O(n) efficiency

int getHighestNumber(ArrayList<Integer> list)
    {       
        if(list != null && list.size() > 0)
        {
            if(list.size() == 1)
                return list.get(0);

            int maxNum = list.get(0);
            for(int item:list)
            {
                if(item > maxNum)
                    maxNum = item;
            }
            return maxNum;          
        }
        return null;
    }

My question is "Can any sorting algorithm beat it (on time scale) on any given input for eg. if the collection is already sorted or not?" Is there any other way better than this ?

Answer 1

If the Collection is already sorted, you can find the largest element in O(1) (assuming the Collection supports random access or O(1) access to the end of the Collection holding the largest element - if the largest element is first, any Collections would give you an O(1) access to it via its Iterator). In that case you don't have to sort it, though.

Any sorting would take at least O(n) when the input is sorted (and at least O(nlog(n)) when it's not), since you can't verify that the input is sorted without going over all the elements. Therefore sorting algorithms cannot beat your O(n) solution.

Answer 2

Your question hints at it's own answer. It depends on the source of the collection itself. That is, the more you know about the data set, the quicker you can devise heuristics to get to the answer you need.

So, if your list is already sorted, then list[0] or list[len-1] will be the highest...

The secondary answer is also dependent on 'How often will the list be searched?'. If this is a one-off search, then just iterating the list for the highest will be fastest. If you will be doing it repeatedly (eg, gathering various metrics), then sorting it first, using Quick Sort, might be your best best.