Finding the largest value in an array and efficiency of code

user_13614022 0
Viewed 73

I want to know if my concept and understanding of the code is correct or not! Here, at first, I set the last number as the max, and then I am using another for loop to compare each value to all other values to find the largest value right? Also is the runtime of this is O(n^2) since here two for loop is used? I know there exists a better linear solution(O(n)) but I want to manually see and check how much time it will take to execute it and also trying to compare the efficiency between two. I also do not know what is the space complexity of this code. Any further explanation will be greatly appreciated.

 /*The following code will return the largest value in an array of non-negative integers */
int CompareToAll (int array[], int n)
{
    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];
    }
space-complexity data-structures time-complexity arrays algorithm
3 Answers

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.

user_108864200

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

user_8444160

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;
    }
user_101615670
Related