Question

Leni and n, be two problems such that Πι α,ely n, . Suppose that problem n, can be solved in O(nk) time and the reduction can be done in O(n) time.Show that problem I1 can be solved in O(ay time 1

Answer 1

Since the problem $\Pi_1$ is polynomial time reducible to $\Pi_2$ , so problem $\Pi_1$ can be solved using pseudo code of $\Pi_2$ as the subroutine by reducing the problem instance of $\Pi_1$ into problem instance of $\Pi_2$ and then performing algorithm of $\Pi_2$ over reduced problem instance of $\Pi_1$ . In this way we will get solution of $\Pi_1$ .

Time complexity :- Reducing problem instance of $\Pi_1$ into equivalent problem instance of $\Pi_2$ will take $O(n^j)$ time and then performing algorithm $\Pi_2$ which has complexity $O(n^k)$ will take total time complexity equal to $O(n^j)O(n^k)=O(n^{jk})$ . Which is the upper bound of time complexity.

Please comment for any clarification.