What is the Big O notation for this function? And Why? (Detailed explanation) in

Question

What is the Big O notation for this function? And Why? (Detailed explanation)

int Max_Subsequence_Sum_GREEN(const int A[], const int N) // GREEN
{
   int This_Sum = 0, Max_Sum = 0;

   for (int i = 0; i < N; i++)
   {
       for (int j = i; j<N; j++)
       {
           This_Sum = 0;
           for (int k = i; k <= j; k++)
           {
               This_Sum += A[k];
           }
           if (This_Sum > Max_Sum)
           {
               Max_Sum = This_Sum;
           }
       }
   }
   return Max_Sum;
}

Explanation / Answer

Let for the below function each line execution cost is O(1)

int Max_Subsequence_Sum_GREEN(const int A[], const int N) // GREEN
{
    int This_Sum = 0, Max_Sum = 0; //    O(1)
  
  
  
    for (int i = 0; i < N; i++)    // As this loop will run for N number of times its cost is O(N)
    {
        for (int j = i; j<N; j++) //   As this loop will run from i to N total number of execution of it will be 1+2+3+4+5+....+N = N(N-1)/2 = (N^2 - N)/2 = O(N^2)
        {
            This_Sum = 0;       
            for (int k = i; k <= j; k++) //This loop will run based on the value of i and j and at max when at tends to infinty the execution cost of it will be O(N^3)
            {
                This_Sum += A[k]; // O(1)
            }
            if (This_Sum > Max_Sum)
            {
                Max_Sum = This_Sum;
            }
        }
    }
    return Max_Sum;
}

Summing all the Costs :
O(1) + O(N^3)(all the three loops)

When N tends to infinity O(N^3) will be very large than O(1)

hence the Big O notation of the above function is O(N^3)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.