**1.**

Choose the correct answer for the following statements:

I. The theory of NP–completeness provides a method of obtaining a polynomial time for NP algorithms.

II. All NP-complete problem are NP-Hard.

**2.**

The following are the statements regarding the NP problems. Chose the right option from the following options:

I. All NP-complete problems are not NP-hard.

II. Some NP-hard problems are not known to be NP-complete.

**3.**The time complexity of the shortest path algorithm can be bounded by

**4.**The time taken by NP-class sorting algorithm is

**5.**A problem L is NP-complete iff L is NP-hard and

**6.**

The term ________ refers to all state space search methods in which all children of the E–nodes are generated before any other live node can become the E-node.

**7.**

Which of the following case does not exist in complexity theory?

**8.**

The complexity of linear search algorithm is _________

**9.**

The complexity of Binary search algorithm is _________

**10.**

The complexity of merge sort algorithm is _________