Finding maximum in O(logn) time?

Question

I've always taken it for granted that iterative search is the go-to method for finding maximum values in an unsorted list.

The thought came to me rather randomly, but in a nutshell: I believe I can accomplish the task in O(logn) time with n being the input array's size.

The approach piggy-backs on merge sort: divide and conquer.

Step 1: divide the findMax() task to two sub-tasks findMax(leftHalf) and findMax(rightHalf). This division should be finished in O(logn) time.

Step 2: merge the two maximum candidates back up. Each layer in this step should take constant time O(1), and there are, per the previous step, O(logn) such layers. So it should also be done in O(1) * O(logn) = O(logn) time (pardon the abuse of notation). This is so wrong. Each comparison is done in constant time, but there are 2^j/2 such comparisons to be done (2^j pairs of candidates at level j-th).

Thus, the whole task should be completed in O(logn) time. O(n) time.

However, when I try to time it, I get results that clearly reflect a linear O(n) running time.

size = 100000000 max = 0 time = 556

size = 200000000 max = 0 time = 1087

size = 300000000 max = 0 time = 1648

size = 400000000 max = 0 time = 1990

size = 500000000 max = 0 time = 2190

size = 600000000 max = 0 time = 2788

size = 700000000 max = 0 time = 3586

How come?

Here's the code (I left the arrays uninitialized to save on pre-processing time, the method, as far as I'd tested it, accurately identifies the maximum value in unsorted arrays):

public static short findMax(short[] list) {
    return findMax(list, 0, list.length);
}

public static short findMax(short[] list, int start, int end) {
    if(end - start == 1) {
        return list[start];
    }
    else {
        short leftMax = findMax(list, start, start+(end-start)/2);
        short rightMax = findMax(list, start+(end-start)/2, end);
        return (leftMax <= rightMax) ? (rightMax) : (leftMax);
    }
}

public static void main(String[] args) {
    for(int j=1; j < 10; j++) { 
        int size = j*100000000; // 100mil to 900mil
        short[] x = new short[size];
        long start = System.currentTimeMillis();
        int max = findMax(x);
        long end = System.currentTimeMillis();
        System.out.println("size = " + size + "\t\t\tmax = " + max + "\t\t\t time = " + (end - start));
        System.out.println();
    }
}

Answer 1

You should count the number of comparisons that actually take place :

In the final step, after you find the maximum of the first n/2 numbers and last n/2 nubmers, you need 1 more comparison to find the maximum of the entire set of numbers.

On the previous step you have to find the maximum of the first and second groups of n/4 numbers and the maximum of the third and fourth groups of n/4 numbers, so you have 2 comparisons.

Finally, at the end of the recursion, you have n/2 groups of 2 numbers, and you have to compare each pair, so you have n/2 comparisons.

When you sum them all you get :

1 + 2 + 4 + ... + n/2 = n-1 = O(n)