Question

a.) What are the tight lowerbound of the comparison based sorting problem and searching problem respectively.

b.) True or False: A P problem is one that can be solved in polynomial time. while a NP problem is one that cannot be solved in polynomial time.Tell the relationship between P and NP problems

Answer 1

Answer to a:

Comparison based sorting can be viewed abstractly as a decision tree problem. Let us assume is as a full binary tree. Each leaf of the decision tree will correspond each of the n! permutations of the n numbers. Each internal node will be a comparison between a_i and a_j element of the list. Left subtree dedicates subsequent consequences if a_i <= a_j. The right subtree will dedicate subsequences for a_i > a_j.

Let x be the maximum number of comparisons. So x is the height of the tree. So with maximum of leaves.

Now,

n! <=

Taking log₂ on both sides

log₂(n!) <= x

Since log₂(n!) = (nlog₂n)

So we can say lower bound is (nlog₂n)

The tight lower bound cost of searching algorithm is O(n) when the list is unsorted. Because to search we need to travel the entire list, otherwise we can not make the comparison. Now, if the list is sorted, then the lowest bound is O(log n).

Answer to b:

The statement is FALSE.

P problem can be solved in polynomial time.

NP problem(stands for Non deterministic polynomial) is solvable in polynomial time in non deterministic Turing machine.

Every decision problem that is solved by a deterministic polynomial time algorithm is also solved by a polynomial time non deterministic algorithm.

All P problems are solved in Polynomial time, whereas NP-P are intractable.

It is not known if P=NP. If P NP, then P is a subset of NP.