Question: The data in Figure shows the result of running the maximum subsequence sum problem in 1991. The program was written in the C programming language and run on a Unix-based Sun 3/60 workstation with 4 Megabytes of main memory. This is the actual data from that era.
a. Verify that for each algorithm, the change in the observed running time is consistent with the Big-Oh running time of the algorithm.
b. Estimate the running time for N = 100,000 for the poorest performing algorithm.
c. How much faster is the algorithm compared to 1991?
d. How much faster is the algorithm compared to 1991?
e. Explain why the answers for parts c and d are different. Is this significant for two algorithms with different Big-Oh running times? Is this significant for two algorithms with identical Big-Oh running times?
