Made Easy Test Series 2024

Question

Suppose we have a directed graph G = (V,E) with V= {1, 2, ..., n} and Eis presented as an adjacency list. For each vertex u in V, out(u) is a list such that (u, v) in {1, 2, ... k). For each u in V, we wish to compute a corresponding list in(u) =such that in E for each i in {1, 2, ... k'). Let n be the number of vertices in Vand m be the number of edges in E. How long would it take to construct the lists in(u), u in V, from the lists out(u), u in V?

• A. T(n) =O(n+m)            B. T(n)= O(n(m+n))

 

Answer 1

question is about finding the in-degree and out-degree or vertices .

to find in-degree and out-degree TC = O (V + E)  where V is no of vertices and E no of edges.(using adjacency list).

 

Ans : O( m + n)