Repeat report 1 for a O(n) solution.
Your report should be cumulative. Include the old section discussing the O(n^3) solution, the second O(n^2) solution, the O(nlogn) solution and your new O(n) solution.
Include a program correctness analysis to prove that your solution solves the problem.
Include a plot showing the runtime experiments for all four solutions.