Skip to content
GATETECH
Official PYQ · 1997Q1.5Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 1997 Q1.5 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

The correct matching for the following pairs is A.All pairs shortest path1.GreedyB.Quick Sort2.Depth-First SearchC.Minimum weight spanning tree3.Dynamic ProgrammingD.Connected Components4.Divide and Conquer\begin{array}{|ll|ll|}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\ \hline \text{B.} & \text{Quick Sort} & \text{2.}& \text{Depth-First Search} \\ \hline \text{C.}& \text{Minimum weight spanning tree} & \text{3.} & \text{Dynamic Programming} \\ \hline \text{D.} & \text{Connected Components} &\text{4.} & \text{Divide and Conquer} \\ \hline \end{array}

Choose one option
View worked solution

Answer: B

We can determine the correct matching by analyzing the design paradigm or algorithmic technique associated with each problem:

  • A. All pairs shortest path (3): The standard algorithm for this problem is the Floyd-Warshall algorithm, which is a classic example of Dynamic Programming.
  • B. Quick Sort (4): Quick Sort works by partitioning an array into subarrays around a pivot and recursively sorting them, which is a textbook Divide and Conquer strategy.
  • C. Minimum weight spanning tree (1): Algorithms like Kruskal's and Prim's construct the minimum spanning tree by making locally optimal choices at each step, which is a Greedy approach.
  • D. Connected Components (2): Finding connected components in a graph is typically done using graph traversal algorithms, such as Depth-First Search (DFS) or Breadth-First Search (BFS).

Thus, the correct matching is:
A-3, B-4, C-1, D-2, which corresponds to Option B.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions