INTRODUCTION TO COMPILER DESIGN
OVERVIEW OF COMPILERS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
cubic
|
|
|
quadratic
|
|
|
linear
|
|
|
logarithmic
|
Detailed explanation-1: -4. The topological sorting of any DAG can be done in time. Explanation: Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.
Detailed explanation-2: -A topological sort of a DAG G = ( V, E ) is a linear ordering of v V such that if ( u, v ) E then u appears before v in this ordering. If G is cyclic, no such ordering exists: Topological sort can also be viewed as placing all the vertices along a horizontal line so that all directed edges go from left to right.
Detailed explanation-3: -The time complexity of topological sort using Kahn’s algorithm is O(V+E), where V = Vertices, E = Edges.
Detailed explanation-4: -So topological sorts only apply to directed, acyclic (no cycles) graphs-or DAGs.