Analyze each of the three algorithms in source code form. To analyze an algorith
ID: 3905242 • Letter: A
Question
Analyze each of the three algorithms in source code form.
To analyze an algorithm by giving the upper bound in "Big-Oh" notation on the execution time of the algorithm and briefly explain your reasoning.
// Algorithm #1
int Max_Subsequence_Sum( const int A[], const int N )
{
int This_Sum = 0, Max_Sum = 0;
for (int i=0; i<N; i++)
{
This_Sum = 0;
for (int j=i; j<N; j++)
{
This_Sum += A[j];
if (This_Sum > Max_Sum)
{
Max_Sum = This_Sum;
}
}
}
return Max_Sum;
}
************************************************************************************************ ********************************************************** **********************************************************
// Algorithm #2
int Max_Subsequence_Sum( const int A[], const int N )
{
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;
}
****************************************************************************************************************************************************************************************************************************
// Algorithm #3
int Max_Subsequence_Sum( const int A[], const int N )
{
int This_Sum = 0, Max_Sum = 0;
for (int Seq_End=0; Seq_End<N; Seq_End++)
{
This_Sum += A[Seq_End];
if (This_Sum > Max_Sum)
{
Max_Sum = This_Sum;
}
else if (This_Sum < 0)
{
This_Sum = 0;
}
}
return Max_Sum;
}
please give a detailed answer.
Explanation / Answer
1.
int Max_Subsequence_Sum( const int A[], const int N ) // It runs for 1 time so its complexity is O(1)
{
int This_Sum = 0, Max_Sum = 0; // It runs for 1 time so its complexity is O(1)
for (int i=0; i<N; i++) // It runs for n times so its complexity is O(n)
{
This_Sum = 0; // It runs for n times so its complexity is O(n)
for (int j=i; j<N; j++) // j loop runs for nearer to n times so its complexity is O(n) and j loop runs for every value of i so its overall complexity is O(n2).
{
This_Sum += A[j]; // Its complexity is O(n2)
if (This_Sum > Max_Sum) // Its complexity is O(n2)
{
Max_Sum = This_Sum; // Its complexity is O(n2)
}
}
}
return Max_Sum; // It runs for 1 time because it returns 1 value so its complexity is O(1)
}
The overall complexity is O(n2).
2.
int Max_Subsequence_Sum( const int A[], const int N ) // It runs for 1 time so its complexity is O(1)
{
int This_Sum = 0, Max_Sum = 0; // It runs for 1 time so its complexity is O(1)
for (int i=0; i<N; i++) // It runs for n times so its complexity is O(n)
{
for (int j=i; j<N; j++) // j loop runs for nearer to n times so its complexity is O(n) and j loop runs for every value of i so its overall complexity is O(n2).
{
This_Sum = 0;
for (int k=i; k<=j; k++) // k loop runs for nearer to n times so its complexity is O(n) and k loop runs for every value of i and j so its overall complexity is O(n3).
{
This_Sum += A[k]; // its complexity is O(n3).
}
if (This_Sum > Max_Sum) // Its complexity is O(n2)
{
Max_Sum = This_Sum; // Its complexity is O(n2)
}
}
}
return Max_Sum; // It runs for 1 time because it returns 1 value so its complexity is O(1)
}
The overall complexity of the program is O(n3).
3.
int Max_Subsequence_Sum( const int A[], const int N ) // It runs for 1 time so its complexity is O(1)
{
int This_Sum = 0, Max_Sum = 0; // It runs for 1 time so its complexity is O(1)
for (int Seq_End=0; Seq_End<N; Seq_End++) // It runs for n times so its complexity is O(n)
{
This_Sum += A[Seq_End]; // It runs for n times so its complexity is O(n)
if (This_Sum > Max_Sum) // It runs for n times so its complexity is O(n)
{
Max_Sum = This_Sum; // Its complexity is O(n)
}
else if (This_Sum < 0) // Its complexity is O(n)
{
This_Sum = 0; // Its complexity is O(n)
}
}
return Max_Sum; // It runs for 1 time because it returns 1 value so its complexity is O(1)
}
The overall complexity of the program is O(n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.