Reference no: EM13944362

Let P be a minimization problem. For each instance x of P there are several feasible solutions. Each feasible solution s has a cost cost(s) and we want to find a solution of x with the minimum cost. We know the cost of each feasible solution for an instance of size n is an integer between 1 and n4. We do not know how to solve p, but we have access to an algorithm A that solves the decision version of 77: Given an instance x of P and an integer k, it returns "Yes"if there exists a feasible solution for x with cost at most k and returns "No" Otherwise. The running time of A on an input of size n is e(n log n). Given an input x of size n, give an algorithm that runs in time 0(n log2 n) and finds the cost of an optimal solution for x.