GATE Overflow Test Series | Algorithms | Test 2 | Question: 11

Question

If the worst case time complexity by the best algorithm for finding the outdegrees and indegrees of all the vertices (extra space can be used if required) in a dense graph of $n$ vertices (number of edges $= \Theta(n^2))$ represented in Adjacency List format is given by $\Theta(n^a \log ^b n)$ and $\Theta(n^c \log ^d n)$ respectively, $2\times a + 3 \times b + 5 \times c + 7 \times d = $ _____

Answer 1

The out-degree of each vertex will be the number of vertices in its adjacency list. So, for all the vertices, we can get the out-degree in $\Theta(m+n)$ time where $m$ is the number of edges. Since $ m = \Theta(n^2),$ this will give $\Theta(n^2).$

In-degree can also be computed in $\Theta(m+n)$ time by maintaining an array of size $n$ for the vertices and then traversing all the adjacency lists. Whenever we encounter a vertex we increment the corresponding entry in the array.

Thus, we get $a = c = 2, b = d = 0.$

$2\times a + 3 \times b + 5 \times c + 7 \times d = 14.$

Comments

if adjacency list is also giving O(n^2) time complexity then wht is the significance ot use over adjacency matrix ?

---

Yes , i think in degree should be Θ(mn) here edges is  Θ(n^2) so answer should be  Θ(n^3) and final answer as 19 not 14 

 

 https://www2.cs.duke.edu/courses/cps130/summer02/Homeworks/Solutions/H19-solution.pdf

also this 

http://www.bowdoin.edu/~ltoma/teaching/cs231/fall09/Homeworks/old/rest/H10-sol.pdf

---

so we can’t assume we have list.size available….!