Complexity Theory Questions

MCQ bookmark_border

1.

Choose the correct answer for the following statements: 

I. The theory of NP

A

I is FALSE and II is TRUE

B

I is TRUE and II is FALSE

C

Both are TRUE

D

Both are FALSE

Correct Answer: A

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

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.

A

Both (I) and (II) are true

B

Both (I) and (II) are false

C

Only (I) is true

D

Only (II) is true

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

3.

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

A

O(n2)

B

O(n4)

C

O(n3)

D

O(n)

E

O(n log n ).

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

4.

The time taken by NP-class sorting algorithm is

A

O(1)

B

O(log n)

C

O(n2)

D

O(n)

Correct Answer: D

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

5.

A problem L is NP-complete iff L is NP-hard and

A

L ? NP

B

L ? NP

C

L ? NP

D

L = NP

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

6.

The term ________ refers to all state space search methods in which all children of the E

A

Backtacking

B

Depth First Search

C

Branch and Bound

D

Breadth First Search

Correct Answer: C

None.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

7.

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

A

Best case

B

Worst case

C

Average case

D

Null case

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

8.

The complexity of linear search algorithm is _________

A

O(n)

B

O(log n)

C

O(n²)

D

O(n log n)

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

9.

The complexity of Binary search algorithm is _________

A

O(n)

B

O(log)

C

O(n²)

D

O(n log n)

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

The complexity of merge sort algorithm is _________

A

O(n)

B

O(log n)

C

O(n²)

D

O(n log n)

Correct Answer: D

Check Answer report_problem Report forum Discussion