Algorithms Algorithms 2

Question 1

Which sorting algorithm has the best average-case time complexity?

Accepted Answer

Merge Sort

Answer

Merge Sort achieves O(n log n) average-case time, which is optimal for comparison-based sorting.

Question 2

In Dijkstra's algorithm, what data structure is typically used to efficiently select the next minimum-distance vertex?

Accepted Answer

Min-Heap (Priority Queue)

Answer

A min-heap allows extracting the minimum-distance unvisited vertex in O(log n) time, making Dijkstra's run in O((V+E) log V).

Question 3

What is the time complexity of the Floyd-Warshall algorithm?

Accepted Answer

O(V³)

Answer

Floyd-Warshall uses three nested loops over all vertices, resulting in O(V³) time complexity.

Question 4

Which algorithm strategy does the 0/1 Knapsack problem use?

Accepted Answer

Dynamic Programming

Answer

0/1 Knapsack uses dynamic programming to build an optimal solution by storing results of overlapping subproblems.

Question 5

What is the worst-case space complexity of recursive Merge Sort?

Accepted Answer

O(n)

Answer

Merge Sort requires O(n) auxiliary space for the temporary arrays used during merging.

Algorithms Practice Test