Report # 2

    Problem

Repeat report 1 for a O(n^2) solution.

Your report should be cumulative. Include the old section discussing the O(n^3) solution and a new O(n^2) solution.

If your original solution was better than O(n^3), then report on your original solution vs. the O(n^3) solution.

Recall that the O(n^3) "brute force" solution can be expressed in peudo-code as

 

maxsofar = 0

for i = [0,n)

    for j = [i,n)

        sum = 0 

        for k = [i,j]

            sum += x[k]

        maxsofar = max(maxsofar,sum) 

 

 

In order to get a quadratic solution its important to recognize that the sum of x[i..j] is closely related to the sum of x[i...j-1]. So, we can reduce the algorithmic complexity by exploiting this observation.

maxsofar = 0

for i = [0,n)

      sum = 0

    for j = [i,n)

         sum += x[j]

         maxsofar = max(maxsofar,sum)

 

Include a more detailed analysis of both algorithms, in terms of the Big-Oh runtime.

Include a plot showing the runtime experiments for both solutions.

Include a table of the following form comparing the two algorithms based on your analysis:

 

  ALG 1 ALG 2
Runtime estimate (a function of "n")    
Estimated iime to solve a problem of size 10^3

10^4

10^5

10^6

10^7

 

   
Max size of problem solved in one sec

min

hr

day

   
If n is multiplied by 10, time multiplies by      
If time multiplies by 10, n multiplies by