What is the time complexity of topological sorting of a directed acycl — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2023 paper

Module 3: Graph and Tree Algorithms

20232m

What is the time complexity of topological sorting of a directed acyclic graph (DAG) with $V$ vertices and $E$ edges using Depth-First Search (DFS)?
(i) $O(V^2)$
(ii) $O(E^2)$
(iii) $O(V+E)$
(iv) $O(V.E)$

Search Google Ask AI

Similar questions

Design and Analysis of Algorithms Topological sorting is only possible in: (i) Undirected Graphs (ii) Trees (iii) Directed Acyclic Graphs (iv) Weighted Graphs20242m Formal Language & Automata TheoryThe construction time for DFA from an equivalent NFA (m number of node) is (i) O(m^2) (ii) O(2^m) (iii) O(m) (iv) O(\log m)20212m FORMAL LANGUAGE & AUTOMATA THEORYThe construction time for DFA from NFA with m nodes is: (i) O(m^2) (ii) O(2^m) (iii) O(m) (iv) O(\log m)20212m Design and Analysis of Algorithms In an unweighted graph, which algorithm is guaranteed to find the shortest path between two nodes? (i) Depth First Search (ii) Kruskal's Algorithm (iii) Breadth First Search (iv) Prim's Algorithm20252m

PreviousIn which algorithmic strategy are problems systematically divided into smaller subproblems until the solution to the original problem is found? (i) Brute-force (ii) Greedy (iii) Dynamic programming (iv) Backtracking NextWhat is the relationship between NP and P complexity classes? (i) P is a subset of NP (ii) NP is a subset of P (iii) P and NP are equivalent (iv) P and NP are disjoint sets