Finding the largest value in an array and efficiency of code

Yes, pessimistic complexity of this algorithm is O(n^2), optimistic is O(n).

Optimistic

First/last element is the largest. In such case only single pass (by either loop) will be done so each element will be visited only once.

Pessimistic

Middle element is the largest. In such case outer loop will run n/2 times and inner loop n/2 times until the half of the array is reached by the outer loop.

This gives us 1/2 * n * 1/2 * n which is O(n^2) as the constant does not matter.

This is also your average as we have no assumption about your data to use here.

O(n) solution

Go from either end of the array and keep the maximum value seen and switch if bigger is found. Return biggest after all elements were visited.

Time complexity is O(n^2) in average case and in the worst case.

Note that this algo has the best case with complexity O(n) (when ``isMax is found at the first iteration(s)).

Space compexity is O(1) - you use only constant space not depending on array size

As you're using an array, the notation for the space complexity would be equivalent to the time complexity. Hence In your case the space complexity would be O(n^2).

An O(n) algorithm would be alongside with its comparison for array lengths upto 1000000 in nanoseconds would be: However, the timing seems to not be working correctly as it varies too much. But yeah, it should be something like this.

Time taken with array size 10 O(n) algorithm 0 nanoseconds O(n^2) algorithm 0 nanoseconds

Time taken with array size 100 O(n) algorithm 0 microseconds O(n^2) algorithm 0 microseconds

Time taken with array size 1000 O(n) algorithm 4 microseconds O(n^2) algorithm 5 microseconds

Time taken with array size 10000 O(n) algorithm 39 microseconds O(n^2) algorithm 48 microseconds

Time taken with array size 100000 O(n) algorithm 2293 microseconds O(n^2) algorithm 4189 microseconds

Time taken with array size 1000000 O(n) algorithm 3271 microseconds O(n^2) algorithm 9715 microseconds

    #include <algorithm> 
    #include <chrono> 
    #include <iostream> 
    using namespace std; 
    using namespace std::chrono; 

    // O(n)
    int findMax(int arr[], int n){

        int maxindex = -1; // to return the position of the maximum value 
        int maxvalue = -1; // // negative hence smallest number amongst positive integers 
        for(int i=0 ; i< n ; i++ ){
    if(arr[i] > maxvalue) {
        maxvalue = arr[i]; // storing max value for next comparison 
        maxindex = i ; //stopring max index to return 
    }
} 
        if( maxindex<0 ) return -1; //list full of negative values 
        return arr[maxindex];

    }

    // O(n^2)
    int CompareToAll(int array[], int n) // your algorithm 
    {
int i, j;
bool isMax;
if (n <= 0)
   return -1;
for (i = n-1; i > 0; i--) {
     isMax = true;
     for (j = 0; j < n; j++) {
        if (array[j] > array[i]) {
           isMax = false;
           break;
        }
     }
             if (isMax) break;
        }

        return array[i];
    }





    int main()
    {
for (int i=10 ; i<=1000000; i=i*10){
int arr[i];

for(int j =0 ; j<i ; j++ ){
    arr[j] = j*2 ; 
}
cout<< endl << "Time taken with array size " << i; 
// Get starting timepoint 
auto start_n = high_resolution_clock::now(); 
findMax(arr,i); 
auto end_n = high_resolution_clock::now();
cout<<endl;
auto duration = duration_cast<microseconds>(end_n - start_n); 
cout<<"O(n) algorithm " <<duration.count() << " nanoseconds"<<endl;


// Get starting timepoint 
auto start = high_resolution_clock::now(); 
CompareToAll(arr,i);
auto end = high_resolution_clock::now();
auto duration2 = duration_cast<microseconds>(end - start); 
cout<< "O(n^2) algorithm " << duration2.count()<< " nanoseconds";
cout<<endl; 
cout<< "------------------";
};
return 0;
    }