Consider the language: A = {<G> | G is a connected undirected graph} and conside

Question

Consider the language: A = {<G> | G is a connected undirected graph} and consider the following algorithm to decide A.

M = “On input <G>m the encoding of a graph G”

1.Select the first node of G and mark it.

2.Repeat the following stage until no new nodes are marked

2a. For each node in G, mark it if it is attached by an edge to a node that is already marker

3. Scan all nodes of G to determine whether they are all marked. If they are, accept; otherwise, reject.

Analyze this algorithm and compute the Big-O complexity.

Explanation / Answer

the complexity of this code is o(n2)

where n is the number of nodes in the graph

since the given grapgh is unidirected graph it may happen that each nodes are connected to each other so if there are n nodes then from 1 node we can reac (n-1) number of nodes

so by checing the algo logic

we are traversing each node connected to the node and coloring it

so comlexity is o(n2)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects