retagged by
373 views
0 votes
0 votes
What is the time complexity of best algorithm that decides whether a given directed

graph represented as adjacency Matrix contains a sink or not ?

(a)O(V^2)

(b)O(VlogV)

(c)O(V^2logV)

(d)O(V)
retagged by

1 Answer

0 votes
0 votes
To decide whether a $sink$ exists from an adjacency matrix, we need to traverse the whole matrix in the worst case. So the best algorithm requires $O(V^2)$ comparisons.

On the other hand, to find if a $universal\space sink$ exists from an adjacency matrix, the best algorithm requires $O(2V) = O(V)$ operations only, as we can skip each row and column on one comparison.

So, the answer is, $a$) $O(V^2).$

Related questions

1.2k
views
1 answers
0 votes
jenny101 asked Oct 26, 2016
1,188 views
586
views
2 answers
0 votes
Pratik.patil asked Aug 31, 2023
586 views
Consider a relation R(A,B,C,D,E,F,G) and the following functional dependencies: (B->D, D->E, AB->C, AE-F, C -> A, F -> G } and choose the ... prime attributes(B) Only B and C are prime attributes(C) Only A, B and F are prime attributes
370
views
0 answers
0 votes
Neelu Lalchandani asked Nov 2, 2022
370 views
Time Complexity in C will be O(n) right? and big omega (n) is also big omega (n^2), then why is c incorrect?