For each of the three methods, explain why the number of array additions A(N) do

Question

For each of the three methods, explain why the number of array additions A(N) done for a length N array has computational complexity of O(N) for one method, O(N^2) for another, and O(N^3) for the third, where N = arr.length.

You don't need to give a rigorous argument here; just reason about the given code and how many times the statement adding an array element to a sum is performed. You could drag out a lot of combinatorial calculations and calculate numAdds exactly as a function of N – but you can just reason here "approximately", instead.


import java.util.Random;
//import java.lang.Math.max;
import java.util.Scanner;

public class MaxSumMain
{

public static void main (String[] args)
{


int size;
Scanner keyboard= new Scanner(System.in);
System.out.println("how big do you want the array to be?");
size = keyboard.nextInt();

int[] arrgh = new int[size];
populate(arrgh);
RunTest(arrgh);

part2();

}

public static void part2()
{
int[] int[128];
int[] two = new int[256];
int[] thr = new int[512];
int[] fou = new int[1024];
int[] fiv = new int[2048];
int[] six = new int[4096];
populate(one);
populate(two);
populate(thr);
populate(fou);
populate(fiv);
populate(six);
RunTest(one);
RunTest(two);
RunTest(thr);
RunTest(fou);
RunTest(fiv);
RunTest(six);
}

public static void RunTest(int[] bobbi)
{
int sub1, sub2, sub3;
sub1 = maxSubSum1(bobbi);
System.out.println("maxSubSum1: " + sub1 + " ");
sub2 = maxSubSum2(bobbi);
System.out.println("maxSubSum2: " + sub2 + " ");
sub3 = maxSubSum3(bobbi);
System.out.println("maxSubSum3: " + sub3 + " ");

if(sub1 == sub2 && sub2 == sub3)
{

}
else System.out.println("computational error, sub array max values did not match");


}

public static void populate(int[] bob)
{
Random R = new Random();
for(int i = 0; i
bob[i] = R.nextInt(500);
}




public static int maxSubSum1 (int[] arr)
{
double operations = 0;

int size = arr.length;

int maxSum = -1;

for (int i = 0; i < size; i++)
for (int j = i; j < size; j++)
{
int thisSum = 0;

for (int k = i; k <= j; k++){
thisSum += arr[k];
operations++;
}
if (thisSum > maxSum)
maxSum = thisSum;
}
System.out.println("number of operations = " + operations + " for array length: " + arr.length);
return maxSum;
}

public static int maxSubSum2 (int[] arr)
{
double operations = 0;
int size = arr.length;

int maxSum = -1;

for (int i = 0; i < size; i++)
{
int thisSum = 0;

for (int j = i; j < size; j++)
{
thisSum += arr[j];
operations++;
if (thisSum > maxSum)
maxSum = thisSum;
}
}
System.out.println("number of operations = " + operations + " for array length: " + arr.length);
return maxSum;
}

public static int maxSubSum3 (int[] arr)
{
double operations = 0;
int size = arr.length;

int maxSum = -1;
int thisSum = 0;

for (int j = 0; j < size; j++)
{
thisSum += arr[j];
operations++;

if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
System.out.println("number of operations = " + operations + " for array length: " + arr.length);
return maxSum;
}

}

Explanation / Answer

Dear.. Method 1: public static int maxSubSum1( int [] a) { int maxSum = 0; for (int i=0; i b ? a > c ? a : c : b > c ? b : c; } when the max sum subsequence is across and must be in it. so we can maximize separately the part that is left of center and ends at Acenter and the part that is right of center and starts at Acenter+1 . Recurrence relation: T(N) = 2 T(N/2) + c N So running time of this method is O(n log n)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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