Write a functional C++ program to display the following output:

Given a rod of length n inches and a table of prices p_i for i = 1, 2, ...,n, determine the maximum revenue r_n obtainable by cutting up the rod and selling the pieces. Note that if the price p_n for a rod of length n is large enough, an optimal solution may require no cutting at all.

Your program must output the running time for rod-lengths of 1 to 30.

Include the running-time behavior, expressed as Big-O.

Requirements:

1.) C++ code that displays the optimal revenue for lengths (n) 1 to 30

2.) For each length, the code must display the run-time for the algorithm (note: I am not interested in run-time for the entire program, only the cut-rod algorithm). Your output should be a table with n, optimal revenue, run-time.

3.) An expression of the behavior in terms of Big-O. PROVIDE PROOF/EXPLANATION

p[11] to p[40] = 30

REQUIRED OUTPUT FORMAT: