Different assembly orders potentially have different total testing cost. For example, suppose that the structureconsists of three pieces, and the cost of testing is given by:f(1,2) = 3,f(2,3) = 1, andf(1,3) = 5. Then assembling the first and second pieces first and then joining them with the third has a total testing cost off (1,2) +f(1,3) = 8, whereas assembling the second and third pieces first and then joining them with the firsthas a total testing cost off(2,3) +f(1,3) = 6. Therefore, the second assembly order is preferable. Required:
Design an O(n^3) algorithm to find an assembly order that incurs the least total testing cost. Give a brief argumentof correctness, and analyze the running time.2