In: Computer Science
Question on greedy algorithm.
A sculptor starts with n metal pieces which are to be pairwise forged together until one piece (the sculpture) emerges. The forging process melds two pieces into one with an energy cost directly proportional to the product of the sizes of the two pieces forged together. For example, melding three pieces of sizes x, y and z could be done in different orders, yielding different costs ( x*y + x*y*z OR x*z + x*z*y OR y*z + y*z*x). Write the C-like pseudocode needed to determine the cheapest order of pairwise forging and analyze the complexity of your code.
The solution is sketched in the pictures below.The solution shows a Greedy approach to solve the problem which ultimately leads to sorting the metal pieces according to their sizes.The Time Complexity of the algorithm is thus O(N.logN).