Finding the maximum element in an array in O(log N) time???

This question is not related to any task from any contest rather a question in my head. The question : Find the maximum element in an array. This is a very easy task and can easily be done in O(N). My question is, the function getMax() does the above task in the following code snippet :

int getMax(vector<int> arr,int l,int r) {
    if(l==r || l+1==r) {
        return max(arr[l],arr[r]);
    }
    return max(getMax(arr,l,(l+r)/2),getMax(arr,(l+r)/2,r));
}

To get the max element in the vector v we call getMax(v,0,v.size()-1). Let the time taken by getMax(v,0,v.size()-1) be T(N) where v.size()=N. According to the code snippet T(N) = 2T(N/2) + O(1).
Solving for T(N) we get T(N) = O(log n). Now it seems that this code works in algorithmic time. This is is against my intuition and you may also argue - to find the max in an array we must visit each an every element in the worst case so we can’t find the max in an array better than O(N) time. So my request to everyone would be to please state where I am going wrong, is it my analysis of T(N) or anything else. And thank you for reading this post till the end.

https://stackoverflow.com/a/64523410/900727

1 Like