What is the time complicity for each of them in the worst

Assignment Help Computer Engineering

Reference no: EM132104950

Answer the following Question :

(a) When does a problem belong to P-Class and when does belong NP Class?

(b) Give two P-Class problems, and give two NP-Class problems which no one knows belonging to P-class or not. Give time complicities of each, respectively.

(c) Suppose that A is a problem belonging to P-Class and B is a problem to NP-Class. Does A belong to NP-Class? Does B belong to P-Class?

(d) Let A be a problem satisfying the following conditions

(i) any problem in NP, Class can be reduced to A in polynomial time, and

(ii) A in an NP problem. What class dose A belong to? Answer the following questions:

(a) Selection sort and insertion sort are called force sort. What is the time complicity for each of them in the worst case?

(b) Between selection sort and inspection sort, which is better? Why?

(a) What is the time complexity of Quick sort in is wart case? What is the time complexity of Merge Soft in worst case?

(b) Can Quick Sort run faster Merge-Sort? Why?

Reference no: EM132104950

Questions Cloud

Show the popularity of a baby name for a particular year : They have supplied you with baby name popularity data from 2006 to 2010. The application should ask the user for a Year, Gender, and Name.

What is the rationale that can be adopted in expounding : What is the rationale that can be adopted in expounding on the rising number of mergers with firms or corporations in distinctive industries?

Create a constructor that allows a user of the class : Create a constructor that allows a user of the class to initialize both values.

Stage of completion should the ending : If equivalent units are 15,000 for conversion costs and units transferred out equals 10,000, what stage of completion should the ending work in process be for t

What is the time complicity for each of them in the worst : Suppose that A is a problem belonging to P-Class and B is a problem to NP-Class. Does A belong to NP-Class? Does B belong to P-Class?

Managerial accounting-computing inventory balances : Calculate the product cost per unit and the total cost of the 2,100 units in ending inventory using absorption costing and variable costing. An explanation woul

Markup percentage on total manufacturing costs : If the company desires a 10% rate of return on total assets, what is the markup percentage on total manufacturing costs for the desired profit?

What is a balanced scorecard : What is a balanced scorecard and why is it important to consider both qualitative and quantitative factors in business decision making?

Accreditation but a flair for numbers : former employer used to only have a CFO without any accreditation but a flair for numbers.

User Account

All Pages