Finding a max element in an array in Java

Question

Created the following method:

public static int max(int[] array) {
    int max = Integer.MIN_VALUE;

    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

Question(s):

1. I believe the Big O Notation for this implementation is O(n), am I right?

2. Since this is basically a search algorithm, how to make it faster (e.g. should use recursion) and if so what would the Big O Notation be for the optimized version?

Answer 1

Yes, this is O(n), because you visit every element once. You can't possibly do better than O(n), because there is no way to be sure that you have found the maximum value without inspecting every element. (There are two exceptions. If the array is known to be sorted in some way, then you can skip straight to the maximum. Also, if you ever encounter Integer.MAX_VALUE, you could return early. The latter optimization is probably not worthwhile.) Recursion would not be faster than iteration, and, in general, iteration should be favoured over recursion in Java for performance.

Since Java 8, you can implement this as a one-liner using IntStream.max():

java.util.Arrays.stream(array).max()

Notice that IntStream.max() returns an OptionalInt. Why OptionalInt instead of int? Because the array might be empty. Your code would return Integer.MIN_VALUE in that case. If that is what you consider to be the "correct" behaviour, then you should document it in the JavaDoc.