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

Question

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?

Explanation / Answer

1.1) complexity of selection sort in worst case o(n2)
   complexity of insertion sort in worst case o(n2)

1.2) insertion sort is better since insertion sort find the correct place of the unsorted element in each pass and insert them in the correct order.

1.3) quick sort complexity in worst case is o(n2)

merge sort complexity is o(nlogn) in worst case

1.4) in no case the quick sort is better than the merge sort

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.