Report # 4

    Problem

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.