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 | |||