Algorithms and Complexity MCQs (Part-2)

Which sorting algorithm has the best average time complexity?

A Merge Sort
B Heap Sort
C Quick Sort
D Bubble Sort

What does the “Omega” notation describe in algorithm analysis?

A Best Case
B Worst Case
C Upper Bound
D Exact Bound

Which algorithm is used to find the minimum spanning tree in a graph?

A Dijkstra’s Algorithm
B Bellman-Ford Algorithm
C Floyd-Warshall Algorithm
D Prim’s Algorithm

Which of these problems is classified as NP-Complete?

A Sorting Problem
B Travelling Salesman Problem
C Binary Search
D Linear Search

Which of the following is true about the time complexity of Merge Sort?

A O(n^2)
B O(n)
C O(n log n)
D O(log n)

Which algorithm is based on the principle of “divide and conquer”?

A Quick Sort
B Merge Sort
C Both A and B
D Dijkstra’s Algorithm

What is the primary use of the Binary Search algorithm?

A Sorting
B Searching in a sorted array
C Finding maximum
D Graph traversal

Which algorithm is used for string matching in a text?

A Merge Sort
B Binary Search
C Rabin-Karp
D Floyd-Warshall

Which of the following best describes the complexity class NP?

A Solvable in polynomial time
B Can be verified in polynomial time
C Not solvable
D Always solvable in logarithmic time

What is the purpose of dynamic programming?

A To reduce space complexity
B To solve sorting problems
C To avoid redundant calculations
D To optimize graph traversal

What is the worst-case time complexity of Bubble Sort?

A O(n^2)
B O(n log n)
C O(log n)
D O(n)

Which algorithm is used to find the longest path in a graph?

A Dijkstra’s Algorithm
B Bellman-Ford Algorithm
C Floyd-Warshall Algorithm
D There is no known polynomial-time algorithm

What is a characteristic of a greedy algorithm?

A Solves by choosing the best overall solution
B Always finds an optimal solution
C Makes local choices to build a global solution
D Solves problems in exponential time

What is the primary disadvantage of the Quick Sort algorithm?

A Requires a lot of space
B It has a high worst-case time complexity
C It is not stable
D It is too slow for large inputs

What does the “P” complexity class represent?

A Problems that can be solved in polynomial time
B Problems that can be solved in exponential time
C Problems that are verifiable in polynomial time
D Problems that have no known solution